#include <bits/stdc++.h> #define ll long long #define ld long double #define all(v) begin(v), end(v) #define pi pair<int, int> #define vi vector<int> using namespace std; struct DSU{ int n; vector<int> lab; DSU(int n){ this->n = n; lab.assign(n+1, -1); } void resize(int n){ this->n = n; lab.assign(n+1, -1); } int find(int u){ if(lab[u] < 0) return u; return lab[u] = find(lab[u]); } bool same(int u, int v){ return find(u) == find(v); } void join(int u, int v){ u = find(u), v = find(v); if(u == v) return; if(lab[u] > lab[v]) swap(u, v); lab[u] += lab[v]; lab[v] = u; } }; const int N = 1e5+3; int n, m, q, u[N], v[N], l[N], r[N], mid[N]; vector<int> o[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> q; for(int i = 1; i <= q; i++){ cin >> u[i] >> v[i]; l[i] = m, r[i] = 1; } DSU d(n); for(int LOOP = 17; LOOP; LOOP--){ for(int i = 1; i <= q; i++){ mid[i] = (l[i] + r[i])/2; o[mid[i]].push_back(i); } for(int i = m; i >= 1; i--){ for(int j = i; j <= n; j+=i) d.join(i, j); for(auto x:o[i]){ if(d.same(u[x], v[x])) r[x] = mid[x] + 1; else l[x] = mid[x] - 1; } o[i].clear(); } d.resize(n); } for(int i = 1; i <= q; i++) cout << m-(l[i]-1) << "\n"; return 0; }