#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[100001];
int depth[100001];
int p[100001][20];
int jump[100001][20];
void dfs(int v, int pV){
for(auto [w,d] : adj[v]){
if(w!=pV){
depth[w]=depth[v]+1;
p[w][0]=v;
jump[w][0]=d;
dfs(w,v);
}
}
}
struct DSU{
int n;
vector<int> e;
DSU(int _n){
n=_n;
e.assign(n+1,-1);
}
int find(int v){
return (e[v]<0?v:e[v]=find(e[v]));
}
bool join(int a, int b){
a=find(a);b=find(b);
if(a==b)return 0;
if(e[a]>e[b])swap(a,b);
e[a]+=e[b];
e[b]=a;
return 1;
}
};
int dist(int a, int b){
if(depth[a]<depth[b])swap(a,b);
int ans=100001;
for(int j=19;j>=0;j--){
if((depth[a]-depth[b])&(1<<j)){
ans=min(ans,jump[a][j]);
a=p[a][j];
}
}
if(a==b)return ans;
for(int j=19;j>=0;j--){
if(p[a][j]!=p[b][j]){
ans=min(ans,min(jump[a][j],jump[b][j]));
a=p[a][j];
b=p[b][j];
}
}
return min(ans,min(jump[a][0],jump[b][0]));
}
int main(){
cin.tie(0)->sync_with_stdio(0);
int n,m,q; cin >> n >> m >> q;
DSU dsu(n);
for(int i=m;i>=1;i--){
for(int j=i*2;j<=n;j+=i){
if(dsu.join(i,j)){
adj[i].push_back({j,i});
adj[j].push_back({i,i});
}
}
}
// for(int i=1;i<=n;i++){
// cout << i << ": ";
// for(auto [v,d] : adj[i])cout << '(' << v << ' ' << d << ')';
// cout << '\n';
// }
p[1][0]=1;
depth[1]=1;
jump[1][0]=100001;
dfs(1,0);
for(int j=1;j<20;j++){
for(int i=1;i<=n;i++){
p[i][j]=p[p[i][j-1]][j-1];
jump[i][j]=min(jump[i][j-1],jump[p[i][j-1]][j-1]);
}
}
// for(int i=1;i<=n;i++){
// cout << '\n';
// for(int j=0;j<20;j++){
// cout << jump[i][j] << ' ';
// }
// }
while(q--){
int a,b; cin >> a >> b;
cout << max(1,m-dist(a,b)+1) << '\n';
}
return 0;
}
