#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2*1e5+5, MAX = 17;
int dsup[MAXN], val[MAXN], sparse[20][MAXN], dist[MAXN], e[MAXN], d[MAXN], novo;
int find(int x){
if(dsup[x] == x)return x;
return dsup[x] = find(dsup[x]);
}
void merge(int a, int b, int c){
a = find(a), b = find(b);
if(a == b)return;
sparse[0][a] = sparse[0][b] = dsup[a] = dsup[b] = novo;
val[novo] = c;
e[novo] = a; d[novo] = b;
novo++;
}
void dfs(int s){
if(val[s] == 0)return;
dist[e[s]] = dist[d[s]] = dist[s]+1;
dfs(e[s]); dfs(d[s]);
}
int lca(int a, int b){
if(dist[a] < dist[b])swap(a,b);
int dif = dist[a] - dist[b];
for(int i = 0; i <= MAX; i++)
if(dif & (1<<i))a = sparse[i][a];
if(a == b)return a;
for(int i = MAX; i >= 0; i--)
if(sparse[i][a] != sparse[i][b]){
a = sparse[i][a];
b = sparse[i][b];
}
return sparse[0][a];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,q; cin>>n>>m>>q;
novo = n+1;
for(int i = 1; i <= 2*n; i++)dsup[i] = i;
for(int i = m; i >= 1; i--)
for(int j = i; j <= n-i; j += i)merge(j,j+i,m-i+1);
for(int i = 1; i <= MAX; i++)
for(int j = 1; j < novo; j++)
if(sparse[i-1][j] != 0)sparse[i][j] = sparse[i-1][ sparse[i-1][j] ];
dfs(novo-1);
while(q--){
int a,b; cin>>a>>b;
cout<<val[ lca(a,b) ]<<"\n";
}
}
