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