#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,
tree_order_statistics_node_update>;
#define ll long long
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define all(a) a.begin(),a.end()
// #define int ll
const int mxn = 2e5+10, lg2 = 18;
vector<int> g[mxn];
int suc[mxn][lg2], val[mxn];
int tin[mxn], tout[mxn], tim;
struct DSU{
vector<int> par; int cur;
void init(int n){
par = vector<int>(2*n+10,-1);
cur = n;
}
int get(int u){
if(par[u]<0) return u;
return par[u] = get(par[u]);
}
bool merge(int u, int v, int i){
u = get(u), v = get(v);
if(u==v) return false;
val[++cur] = i;
par[cur] = par[u] + par[v];
par[u] = par[v] = cur;
g[cur].pb(u); g[cur].pb(v);
return true;
}
};
void dfs(int u){
tin[u] = tim++;
for(int i = 1; i < lg2; i++)
suc[u][i] = suc[suc[u][i-1]][i-1];
for(auto v : g[u]){
suc[v][0] = u;
dfs(v);
}
tout[u] = tim;
}
bool isanc(int u, int v){
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int getlca(int u, int v){
if(isanc(u,v)) return u;
if(isanc(v,u)) return v;
for(int i = lg2-1; i >= 0; i--)
if(!isanc(suc[u][i],v))
u = suc[u][i];
return suc[u][0];
}
void solve(){
int n,m,q; cin >> n >> m >> q;
DSU dsu; dsu.init(n);
for(int i = m; i; i--){
for(int j = 2*i; j <= n; j+=i)
dsu.merge(i,j,m-i+1);
}
suc[dsu.cur][0] = dsu.cur;
dfs(dsu.cur);
while(q--){
int u,v; cin >> u >> v;
cout << val[getlca(u,v)] << '\n';
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int t = 1;
while(t--) solve();
}
