#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int dp[20][MAXN], dist[MAXN];
int val[MAXN], lc[MAXN], rc[MAXN];
int krt_pai[MAXN], dsu_pai[MAXN];
int krt_sz;
void init(int v, int t){
dsu_pai[v] = krt_pai[v] = v;
val[v] = t;
}
int get(int v){
if(v == dsu_pai[v]) return v;
return dsu_pai[v] = get(dsu_pai[v]);
}
void add(int a, int b, int t){
a = get(a); b = get(b);
if(a == b) return;
krt_sz ++;
init(krt_sz, t);
lc[krt_sz] = a; rc[krt_sz] = b;
dsu_pai[a] = dsu_pai[b] = krt_sz;
krt_pai[a] = krt_pai[b] = krt_sz;
}
void dfs(int v, int d){
if(!v) return;
dist[v] = d;
dfs(lc[v], d + 1);
dfs(rc[v], d + 1);
}
int lca(int a, int b){
if(dist[a] < dist[b]) swap(a, b);
for(int k=0; k<20; k++){
if((dist[a] - dist[b]) & (1 << k)){
a = dp[k][a];
}
}
if(a == b) return a;
for(int k=19; k>=0; k--){
if(dp[k][a] != dp[k][b]){
a = dp[k][a];
b = dp[k][b];
}
}
return dp[0][a];
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, m, q; cin >> n >> m >> q;
for(int i=1; i<=n; i++) init(i, 0);
krt_sz = n;
for(int i=1; i<=m; i++){
int d = m - i + 1;
for(int j=d; j<=(n - d); j+=d) add(j, j + d, i);
}
dfs(krt_sz, 0);
for(int i=1; i<=krt_sz; i++) dp[0][i] = krt_pai[i];
for(int k=1; k<20; k++){
for(int i=1; i<=krt_sz; i++){
dp[k][i] = dp[k - 1][dp[k - 1][i]];
}
}
while(q--){
int a, b; cin >> a >> b;
cout << val[lca(a, b)] << "\n";
}
return 0;
}
