#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 2e9;
struct DSU {
vector<int> par, sz;
DSU(int n) {
par.assign(n+1, 0);
sz.assign(n+1, 1);
}
void init() {
for (int i = 1; i < par.size(); ++i) {
par[i] = i;
sz[i] = 1;
}
}
int find(int u) {
return (u==par[u] ? u : par[u] = find(par[u]));
}
void unite(int u, int v) {
int a = find(u), b = find(v);
if (a!=b) {
if (sz[a]<sz[b]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
}
}
};
int n, m, q, update;
vector<pair<int, int> > query;
vector<int> ans, ql, qr;
vector<vector<int> > bucket;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
query.assign(q, make_pair(0, 0));
for (int i = 0; i < q; ++i) {
cin >> query[i].first >> query[i].second;
}
ql.assign(q, 1); qr.assign(q, m); ans.assign(q, inf);
bucket.assign(m+1, {});
DSU dsu(n);
while (true) {
update = false;
for (int i = 1; i <= m; ++i) bucket[i].clear();
for (int i = 0; i < q; ++i) {
if (ql[i]<=qr[i]) {
bucket[(ql[i]+qr[i])/2].emplace_back(i);
update = true;
}
}
if (!update) break;
dsu.init();
for (int i = 1; i <= m; ++i) {
int gcd = m-i+1;
for (int j = gcd+gcd; j <= n; j += gcd) {
dsu.unite(j-gcd, j);
}
for (int id : bucket[i]) {
if (dsu.find(query[id].first)==dsu.find(query[id].second)) {
qr[id] = i-1;
ans[id] = min(ans[id], i);
} else ql[id] = i+1;
}
}
}
for (int i : ans) cout << i << "\n";
return 0;
}
