#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 1e5 + 5;
int n, m, q;
vector<int> g[maxn];
pair<int, int> que[maxn];
int ans[maxn];
int le[maxn], ri[maxn];
vector<int> cand[maxn];
struct dsu {
int n;
vector<int> par;
dsu() {}
dsu(int n) : n(n), par(n + 5) {
for(int i = 1; i <= n; ++i) par[i] = i;
}
int find(int u) {
return u == par[u] ? u : par[u] = find(par[u]);
}
void join(int u, int v) {
u = find(u), v = find(v);
if(u == v) return;
par[v] = u;
}
} d;
void solve() {
cin >> n >> m >> q;
for(int i = 1; i <= q; ++i) {
cin >> que[i].first >> que[i].second;
le[i] = 1, ri[i] = m;
ans[i] = -1;
}
while(1) {
bool exist = 0;
for(int i = 1; i <= q; ++i) {
if(le[i] <= ri[i]) {
int mid = (le[i] + ri[i]) >> 1;
cand[mid].push_back(i);
exist = 1;
}
}
if(!exist) break;
d = dsu(n + m);
for(int mid = 1; mid <= m; ++mid) {
int x = m - mid + 1;
for(int j = x; j <= n; j += x) {
d.join(j, x + n);
}
for(auto i:cand[mid]) {
bool flag = d.find(que[i].first) == d.find(que[i].second);
if(flag) {
ans[i] = mid;
ri[i] = mid - 1;
}
else le[i] = mid + 1;
}
cand[mid].clear();
}
}
for(int i = 1; i <= q; ++i) {
cout << ans[i] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
