#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl '\n'
const int N = 1e6 + 5 , M = 1e7 + 5 , MOD = 1e9 + 7;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
struct dsu{
vector<int>size ,par;
dsu(int n ){
size.resize(n+5,1) ;
par.resize(n+5);
for (int i = 1; i <=n ; ++i) par[i] = i;
}
int find_par(int u){
if (par[u] == u) return u;
return par[u] = find_par(par[u]);
}
bool connected(int u , int v){
int par_u = find_par(u) , par_v = find_par(v) ;
return (par_v == par_u);
}
void link (int u , int v){
int par_u = find_par(u) , par_v = find_par(v) ;
if (par_u == par_v) return;
if(size[par_u] > size[par_v]){
// attach comp of v to u (smaller to larger )
// size of u will increase by size of v
size[par_u] += size[par_v] ;
// change the parent of v to be the parent of u
// example if the parent of v = 2 & the parent of u = 8 -> you will make this par[2] = 8
// This mean the node 2 --> 8 and when you go from children of 2 to search about parent you will answer by 8
par[par_v] = par_u;
}
else {
size[par_v] += size[par_u];
par[par_u] = par_v ;
}
}
};
void solve() {
int n, m , q;
cin >> n >> m >> q;
vector<pair<int , int>> qry;
for(int i = 0; i < q; ++i) {
int u , v;
cin >> u >> v;
qry.push_back({u , v});
}
vector<int> l(q , 1) , r(q , m) , ans(q , -1);
while(1) {
bool f = 1;
vector<vector<int>> mids(m + 1);
for(int i = 0; i < q; ++i) {
if(l[i] <= r[i]) {
int mid = (l[i] + r[i]) / 2;
mids[mid].push_back(i);
f = 0;
}
}
if(f)
break;
dsu ds(n);
for(int i = 1; i <= m; ++i) {
int g = m - i + 1;
for(int j = 2; j * g <= n; ++j) {
ds.link(g , g * j);
}
for(auto &idx : mids[i]) {
auto [u , v] = qry[idx];
if(ds.connected(u , v)) {
ans[idx] = i;
r[idx] = i - 1;
}
else
l[idx] = i + 1;
}
}
}
for(auto &x : ans)
cout << x << endl;
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t = 1;
// cin >> t;
while(t--) { solve(); }
return 0;
}
