#include <bits/stdc++.h>
#define lli long long int
#define endl "\n"
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(__null);
using namespace std;
class DSU {
public:
int n;
vector<int> par, sz;
DSU(int m) {
n = m;
par.resize(n), sz.resize(n, 1);
iota(par.begin(), par.end(), 0);
}
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (sz[v] > sz[u]) swap(u, v);
par[v] = u, sz[u] += sz[v];
}
};
signed main() {
fastio()
int n, m, q;
cin >> n >> m >> q;
vector<array<int, 2>> qr(q);
for (auto &[a, b] : qr) cin >> a >> b;
vector<int> lo(q, 1), hi(q, m), ans(q);
for (int i = 1; i <= 17; i++) {
vector<int> check[m + 1];
for (int i = 0; i < q; i++)
if (lo[i] <= hi[i]) check[(lo[i] + hi[i]) / 2].push_back(i);
DSU graph(n + 1);
for (int j = 1; j <= m; j++) {
int f = m - j + 1;
for (int k = 2; k * f <= n; k++) graph.merge((k - 1) * f, k * f);
for (auto &in : check[j]) {
auto &[a, b] = qr[in];
if (graph.find(a) == graph.find(b)) ans[in] = j, hi[in] = j - 1;
else lo[in] = j + 1;
}
}
}
for (auto &x : ans) cout << x << endl;
return 0;
}
