#include <bits/stdc++.h>
#define int long long
std::vector<std::pair<int,int>> adj[100100];
int dsu[100100];
int find(int a){
if(dsu[a]==a)return a;
else return dsu[a]=find(dsu[a]);
}
bool merge(int a,int b){
int A = find(a);
int B = find(b);
if(A==B)return false;
dsu[A]=B;return true;
}
int bilift[100100][23];
int weight[100100][23];
int depth[100100];
void dfs(int curr,int parr,int lw){
depth[curr]=depth[parr]+1;
bilift[curr][0]=parr;
weight[curr][0]=lw;
for(int i=1;i<=20;i++){
bilift[curr][i]=bilift[bilift[curr][i-1]][i-1];
weight[curr][i]=std::max(weight[curr][i-1],weight[bilift[curr][i-1]][i-1]);
}
for(auto [to,w]:adj[curr]){
if(to==parr)continue;
dfs(to,curr,w);
}
}
int lca(int a,int b){
if(a==b)return 0;
int value=0;
if(depth[a]>depth[b])std::swap(a,b);
for(int i=20;i>=0;i--){
if(depth[bilift[b][i]]>=depth[a]){
value=std::max(weight[b][i],value);
b=bilift[b][i];
}
}
if(a==b)return value;
for(int i=20;i>=0;i--){
if(bilift[a][i]!=bilift[b][i]){
value=std::max(weight[a][i],value);
value=std::max(weight[b][i],value);
a=bilift[a][i];
b=bilift[b][i];
}
}
value=std::max(weight[a][0],value);
value=std::max(weight[b][0],value);
return value;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n,m,q;
std::cin >> n >> m >> q;
for(int i=1;i<=n;i++)dsu[i]=i;
for(int i=m;i>=1;i--){
for(int j=i;j+i<=n;j+=i){
if(merge(j,j+i)){
adj[j].push_back({j+i,m-i+1});
adj[j+i].push_back({j,m-i+1});
}
}
}
dfs(1,1,0);
while(q--){
int a,b;
std::cin >> a >> b;
std::cout << lca(a,b) << '\n';
}
}
