#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxk=20;
int pai[2*maxn], krt_pai[2*maxn], cnt, val[2*maxn], dp[2*maxn][maxk], prof[2*maxn];
vector<int>v[2*maxn];
int find(int a){
if(a==pai[a]) return a;
return krt_pai[a]=find(krt_pai[a]);
}
void merge(int a, int b, int c){
a=find(a); b=find(b);
if(a==b) return;
pai[a]=pai[b]=krt_pai[a]=krt_pai[b]=++cnt;
pai[cnt]=cnt;krt_pai[cnt]=cnt; val[cnt]=c;
v[cnt].push_back(a); v[cnt].push_back(b);
}
void dfs(int u, int p){
dp[u][0]=p; prof[u]=prof[p]+1;
for(int k=1;k<maxk;k++) dp[u][k]=dp[dp[u][k-1]][k-1];
for(int viz : v[u]) dfs(viz,u);
}
int lca(int a, int b){
if(prof[a]<prof[b]) swap(a,b);
int d=prof[a]-prof[b];
for(int k=0;k<maxk;k++) if(d&(1<<k)) a=dp[a][k];
if(a==b) return val[a];
for(int k=maxk-1;k>=0;k--){
int na=dp[a][k], nb=dp[b][k];
if(na!=nb) a=na, b=nb;
}
return val[dp[a][0]];
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, m, q; cin >> n >> m >> q;
cnt=n;
for(int i=1;i<=n;i++) pai[i]=krt_pai[i]=i;
for(int i=m;i>=1;i--){
for(int j=i;j+i<=n;j+=i) merge(j,j+i,m-i+1);
}
dfs(cnt,cnt);
while(q--){
int a, b; cin >> a >> b;
cout << lca(a,b) << '\n';
}
}
