#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int mxN = 1e5 + 5;
int n,m,q,ans[mxN],a[mxN],b[mxN],L[mxN],R[mxN];
vector<int> qq[mxN];
struct ds{
vector<int> rank,par;
void init(){
rank.resize(mxN);
par.resize(mxN);
}
void clear(){
for(int i = 0; i <= n; i++){
rank[i] = 0;
par[i] = i;
}
}
ll find(ll at){
if(par[at] == at) return at;
par[at] = find(par[at]);
return par[at];
}
void merge(ll p1, ll p2){
p1 = find(p1); p2 = find(p2);
if(p1 == p2) return;
if(rank[p1] < rank[p2]) swap(p1, p2);
par[p2] = p1;
rank[p1] += (rank[p1] == rank[p2]);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> q;
ds s;
s.init();
for(int i = 0; i < q; i++){
cin >> a[i] >> b[i];
L[i] = 1;
R[i] = m + 1;
qq[1 + m / 2].pb(i);
}
for(int i1 = 0; i1 < 18; i1++){
s.clear();
for(int i = m; i >= 1; i--){
for(int j = i + i; j <= n; j += i) s.merge(i, j);
for(auto it : qq[i]){
if(s.find(a[it]) == s.find(b[it])) L[it] = i;
else R[it] = i;
}
qq[i].clear();
}
for(int i = 0; i < q; i++){
if(R[i] - L[i] == 1) ans[i] = L[i];
else qq[L[i] + (R[i] - L[i]) / 2].pb(i);
}
}
for(int i = 0; i < q; i++) cout << m - ans[i] + 1 << '\n';
}
