#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define eb emplace_back
#define pob pop_back
#define pof pop_front
#define sz(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define iBIT(x) ((x) ? 31 - __builtin_clz(x) : -1)
#define lBIT(x) ((x) ? 63 - __builtin_clzll(x) : -1)
using ll = long long;
template<class T> using vec = vector<T>;
template<class T> using prqm = priority_queue<T, vec<T>, greater<T>>;
template<class T> using prq = priority_queue<T>;
constexpr int mxn = 100005, mxl = 18;
vec<pair<int, int>> adj[mxn];
int n, m, q, up[mxn][mxl], mx[mxn][mxl], p[mxn], dep[mxn] = {};
inline int find(int x) {return (x == p[x]?x:p[x] = find(p[x]));}
inline void add(int a, int b, int w) {
int ra = find(a), rb = find(b);
if(ra^rb) {
p[ra] = rb;
adj[a].pb({b, w});
adj[b].pb({a, w});
}
}
void dfs(int u, int p1, int d, int w) {
dep[u] = d+1, up[u][0] = p1, mx[u][0] = w;
for(int i = 1; i < mxl; ++i) {
up[u][i] = up[up[u][i-1]][i-1];
mx[u][i] = max(mx[u][i-1], mx[up[u][i-1]][i-1]);
}
for(pair<int, int> &e : adj[u]) if(e.fi^p1) dfs(e.fi, u, d+1, e.se);
}
inline int get(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
int d = dep[a]-dep[b], res = 0;
for(int i = mxl-1; i >= 0; --i) {
if(d>>i&1) {
res = max(res, mx[a][i]);
a = up[a][i];
}
}
if(a==b) return res;
for(int i = mxl-1; i >= 0; --i) {
if(up[a][i] && up[a][i]^up[b][i]) {
res = max({res, mx[a][i], mx[b][i]});
a = up[a][i];
b = up[b][i];
}
}
return max({res, mx[a][0], mx[b][0]});
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
iota(p+1, p+n+1, 1);
for(int g = m; g >= 1; --g) {
int d = m-g+1;
for(int v = (g<<1); v <= n; v += g) add(g, v, d);
}
for(int i = 1; i <= n; ++i) if(dep[i] == 0) dfs(find(i), 0, 1, 0);
while(q--) {
int a, b;
cin >> a >> b;
if(find(a)^find(b)) continue;
cout << get(a, b) << '\n';
}
}
