#include <bits/stdc++.h>
using namespace std;
#define int long long
#define i64 long long
/*
* Remember why cp, you aren't Kuhn to match problems with topics.
* If you stuck in problem read it again, if not try to find pattern or solve simple cases.
*/
struct DSU{
vector<int> sz,par;
int N ;
DSU(int N):N(N){
sz = vector<int>(N,1);
for(int i = 0 ; i < N ; i ++) par.push_back(i) ;
}
int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); }
bool inOneSet(int A, int B) { return find(A) == find(B); }
int size(int u) { return sz[find(u)]; }
int sizeU(int u){return sz[u] ;}
bool unit(int A, int B){
A = find(A);
B = find(B);
if (A == B) return false;
if (sz[A] < sz[B]) swap(A, B);
sz[A] += sz[B];
par[B] = A ;
return true ;
}
void clear() {
sz.assign(N, 1) ;
iota(begin((par)), end(par), 0) ;
}
};
void solve() {
int n, m, q ; cin >> n >> m >> q ;
vector<array<int, 2>>qu(q) ;
for (auto &[x, y] : qu) {
cin >> x >> y ;
x -- ; y -- ;
}
vector<int>mids[m], L(q, 0), R(q, m - 1) ;
for (int i = 0 ; i < q ; i ++) mids[(m - 1)/2].push_back(i) ;
DSU d(n) ;
while (true) {
for (int i = 0 ; i < m ; i ++) {
int g = m - i ;
for (int j = g ; j <= n ; j += g) {
d.unit(g - 1, j - 1) ;
}
for (int j : mids[i]) {
auto [u, v] = qu[j] ;
if (d.inOneSet(u, v)) {
R[j] = i - 1 ;
}else {
L[j] = i + 1 ;
}
}
mids[i].clear();
}
int ok = 1 ;
for (int i = 0 ; i < q ; i ++) {
if (L[i] <= R[i]) {
mids[(R[i] + L[i])/2].push_back(i) ;
ok = 0 ;
}
}
if (ok) break ;
d.clear();
}
for (int i : L) cout << i + 1 << '\n' ;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
clock_t start = clock();
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
int tc = 1;
// cin >> tc;
for (int ttt = 1; ttt <= tc; ttt++) {
#ifdef LOCAL
cout << "Case " << ttt << ": ";
#endif
solve();
}
#ifdef LOCAL
clock_t end = clock();
double time_taken = double(end - start) / CLOCKS_PER_SEC;
cout << "\n\n\n\n\nTime taken: " << time_taken << " seconds\n";
#endif
return 0;
}
