#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
using namespace std;
struct DSU {
vector<int> p, d;
DSU(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
d.resize(n);
}
int get_par(int v) {
if (v == p[v]) {
return v;
}
return p[v] = get_par(p[v]);
}
void unite(int u, int v) {
u = get_par(u);
v = get_par(v);
if (u != v) {
if (d[u] > d[v]) {
swap(u, v);
}
p[u] = v;
if (d[u] == d[v]) {
d[v]++;
}
}
}
};
const int LOG = 18;
void dfs(int v, const vector<vector<pair<int, int>>>& gr,
vector<vector<int>>& up, vector<vector<int>>& maxup,
vector<int>& tin, vector<int>& tout, int& timer,
int p, int pedge) {
tin[v] = timer++;
up[v][0] = p;
maxup[v][0] = pedge;
for (int i = 1; i < LOG; ++i) {
up[v][i] = up[up[v][i - 1]][i - 1];
maxup[v][i] = max(maxup[v][i - 1], maxup[up[v][i - 1]][i - 1]);
}
for (const auto& [u, w] : gr[v]) {
if (u != p) {
dfs(u, gr, up, maxup, tin, tout, timer, v, w);
}
}
tout[v] = timer++;
}
inline bool ispar(int u, int v, const vector<int>& tin, const vector<int>& tout) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int maxonpath(int u, int v,
const vector<vector<int>>& up, const vector<vector<int>>& maxup,
const vector<int>& tin, const vector<int>& tout) {
int ans = 0;
if (!ispar(u, v, tin, tout)) {
int u1 = u;
for (int i = LOG - 1; i > -1; --i) {
if (!ispar(up[u1][i], v, tin, tout)) {
ans = max(ans, maxup[u1][i]);
u1 = up[u1][i];
}
}
ans = max(ans, maxup[u1][0]);
}
if (!ispar(v, u, tin, tout)) {
int v1 = v;
for (int i = LOG - 1; i > -1; --i) {
if (!ispar(up[v1][i], u, tin, tout)) {
ans = max(ans, maxup[v1][i]);
v1 = up[v1][i];
}
}
ans = max(ans, maxup[v1][0]);
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<vector<pair<int, int>>> gr(n + 1);
DSU d(n + 1);
for (int i = m; i >= 1; --i) {
for (int j = 2 * i; j <= n; j += i) {
if (d.get_par(i) != d.get_par(j)) {
d.unite(i, j);
gr[i].push_back({ j, m - i + 1 });
gr[j].push_back({ i, m - i + 1 });
}
}
}
vector<vector<int>> up(n + 1, vector<int>(LOG));
vector<vector<int>> maxup(n + 1, vector<int>(LOG));
vector<int> tin(n + 1), tout(n + 1);
int timer = 0;
dfs(1, gr, up, maxup, tin, tout, timer, 1, 0);
for (int i = 0; i < q; ++i) {
int u, v;
cin >> u >> v;
cout << maxonpath(u, v, up, maxup, tin, tout) << '\n';
}
}
