#include <bits/stdc++.h>
using namespace std;
#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
template<class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) {
x = y;
return true;
}
return false;
}
const int MAX_N = (int)1e5 + 5;
int numNode, numDay, numQuery;
struct DSU {
int par[MAX_N], sz[MAX_N];
void init() {
FOR(i, 1, numNode) par[i] = i, sz[i] = 1;
}
int get(int a) {
return (a == par[a] ? a : par[a] = get(par[a]));
}
bool unite(int u, int v) {
u = get(u), v = get(v);
if (u == v) return false;
if (sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
par[v] = u;
return true;
}
} dsu;
vector<ii> MST[MAX_N];
struct LCA {
int par[20][MAX_N], maxVal[20][MAX_N], high[MAX_N];
void dfs(int u, int p) {
for (ii e : MST[u]) {
int v = e.F, w = e.S;
if (v == p) continue;
par[0][v] = u;
maxVal[0][v] = w;
high[v] = high[u] + 1;
dfs(v, u);
}
}
void setup() {
dfs(1, -1);
FOR(i, 1, 18) FOR(u, 1, numNode) {
par[i][u] = par[i - 1][par[i - 1][u]];
maxVal[i][u] = max(maxVal[i - 1][u], maxVal[i - 1][par[i - 1][u]]);
}
high[0] = -1;
}
int getMax(int u, int v) {
if (high[u] < high[v]) swap(u, v);
int ans = 0;
FOD(i, 18, 0) if (high[par[i][u]] >= high[v]) {
maximize(ans, maxVal[i][u]);
u = par[i][u];
}
if (u == v) return ans;
FOD(i, 18, 0) if (par[i][u] != par[i][v]) {
maximize(ans, maxVal[i][u]);
maximize(ans, maxVal[i][v]);
u = par[i][u];
v = par[i][v];
}
maximize(ans, maxVal[0][u]);
maximize(ans, maxVal[0][v]);
return ans;
}
} lca;
void solve() {
cin >> numNode >> numDay >> numQuery;
dsu.init();
FOD(i, numDay, 1) {
for (int j = i + i; j <= numNode; j += i) {
if (dsu.unite(i, j)) {
MST[i].push_back({j, numDay - i + 1});
MST[j].push_back({i, numDay - i + 1});
}
}
}
lca.setup();
while (numQuery--) {
int a, b;
cin >> a >> b;
cout << lca.getMax(a, b) << "\n";
}
}
int32_t main() {
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
bool multitest = 0;
int numTest = 1;
if (multitest) cin >> numTest;
while (numTest--) {
solve();
}
return 0;
}
/* Lak lu theo dieu nhac!!!! */
