#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; }