#include <bits/stdc++.h>
using namespace std;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
// #define int long long
#define fi first
#define se second
#define pb push_back
// #define endl '\n'
typedef pair<int,int> pii;
const int N = 5e5+5;
const int LOG = 20;
int comp[N], pai[N], ans[N], nn;
void createNode()
{
nn++, comp[nn] = pai[nn] = nn;
ans[nn] = 0;
return;
}
int findComp(int u)
{
if(u==comp[u]) return u;
return comp[u] = findComp(comp[u]);
}
bool Join(int u, int v, int x)
{
u = findComp(u);
v = findComp(v);
if(u==v) return false;
createNode();
comp[u] = pai[u] = nn;
comp[v] = pai[v] = nn;
ans[nn] = x;
return true;
}
vector<int> grafo[N];
int lvl[N];
int anc[LOG+1][N];
void DFS(int u)
{
lvl[u] = lvl[pai[u]]+1;
anc[0][u] = pai[u];
for(int k = 1;k <= LOG;k++) anc[k][u] = anc[k-1][anc[k-1][u]];
for(auto v : grafo[u]) DFS(v);
return;
}
int LCA(int u, int v)
{
if(lvl[u]<lvl[v]) swap(u,v);
for(int k = LOG;k >= 0;k--)
if(lvl[anc[k][u]]>=lvl[v])
u = anc[k][u];
if(u==v) return u;
for(int k = LOG;k >= 0;k--)
if(anc[k][u]!=anc[k][v])
u = anc[k][u], v = anc[k][v];
return anc[0][u];
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
for(int i = 1;i <= n;i++) createNode();
for(int i = m;i >= 1;i--)
for(int j = i;j <= n;j += i)
Join(i, j, m-i+1);
for(int i = 1;i < nn;i++) grafo[pai[i]].pb(i);
DFS(nn);
while(q--)
{
int u,v;
cin >> u >> v;
cout << ans[LCA(u,v)] << endl;
}
return 0;
}
