#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double
const int MAXN = 1e5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;
const ld eps = 1e-6;
struct DSU{
ll N;
vector<ll> par;
DSU(ll _n){
N = _n;
par.resize(N + 5);
for(int i = 1; i <= N; i++) par[i] = i;
}
ll find(ll idx){
return (par[idx] == idx ? idx : par[idx] = find(par[idx]));
}
void join(ll a, ll b){
a = find(a), b = find(b);
if(a == b) return;
par[b] = a;
}
};
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for(;tc--;){
ll N, M, Q; cin >> N >> M >> Q;
vector<pair<pii, ll>> query[M + 5][2];
vector<ll> lf(Q + 5), rg(Q + 5), ans(Q + 5);
for(int i = 1; i <= Q; i++){
ll a, b; cin >> a >> b;
if(a != b){
lf[i] = 1, rg[i] = M;
query[(lf[i] + rg[i]) / 2][0].push_back({{a, b}, i});
}
}
for(int log = 1; log < 20; log++){
DSU dsu(N);
for(int i = 1; i <= M; i++){
for(int j = M - i + 1; j <= N; j += M - i + 1){
dsu.join(M - i + 1, j);
}
for(auto [cur, idx] : query[i][(log % 2) ^ 1]){
if(dsu.find(cur.fi) == dsu.find(cur.sec)){
ans[idx] = i;
rg[idx] = i - 1;
}
else lf[idx] = i + 1;
if(lf[idx] <= rg[idx]){
query[(lf[idx] + rg[idx]) / 2][log % 2].push_back({cur, idx});
}
}
query[i][(log % 2) ^ 1].clear();
}
}
for(int i = 1; i <= Q; i++) cout << ans[i] << "\n";
}
}
