#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "local_debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
#define int long long
#define nl '\n'
#define sp ' '
#define F first
#define S second
#define SZ(s) (int)((s).size())
const int N = 1e5 + 5;
pair <int, int> queries[N];
int ql[N], qr[N], ans[N];
struct DSU {
vector <int> par, sz;
DSU(int n) : par(n + 1), sz(n + 1, 1) {
for(int i = 1; i <= n; ++i) par[i] = i;
}
int get(int v) {
return (par[v] == v ? v : (par[v] = get(par[v])));
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if(u != v) {
if(sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
}
}
bool query(int u, int v) {
return get(u) == get(v);
}
};
void solve() {
int n, m, q; cin >> n >> m >> q;
for(int i = 1; i <= q; ++i) cin >> queries[i].F >> queries[i].S;
for(int i = 1; i <= q; ++i) ql[i] = 1, qr[i] = m;
while(1) {
bool done = 1;
vector <int> qm[m + 1];
for(int i = 1; i <= q; ++i) {
if(ql[i] > qr[i]) continue;
done = 0;
qm[(ql[i] + qr[i]) >> 1].push_back(i);
}
if(done) break;
DSU dsu(n);
for(int mid = 1; mid <= m; ++mid) {
int mult = m - mid + 1;
for(int i = mult; i <= n; i += mult) dsu.unite(mult, i);
for(auto i : qm[mid]) {
auto [u, v] = queries[i];
if(dsu.query(u, v)) ans[i] = mid, qr[i] = mid - 1;
else ql[i] = mid + 1;
}
}
}
for(int i = 1; i <= q; ++i) cout << ans[i] << nl;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int tc = 1;
// cin >> tc;
while(tc--) solve();
}
