#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int par[300000], siz[300000];
int get_parent(int v){
if(v == par[v]){
return v;
}
return par[v] = get_parent(par[v]);
}
void merge(int u, int v){
int parent_u = get_parent(u);
int parent_v = get_parent(v);
if(parent_u == parent_v) return;
if(siz[parent_u] < siz[parent_v]){
swap(parent_u, parent_v);
}
par[parent_v] = parent_u;
siz[parent_u] += siz[parent_v];
}
//bool ask(int n, int m, int j, int u, int v){
// for(int i = 0; i <= n; i++){
// par[i] = i;
// siz[i] = 1;
// }
// for(int i = 1; i <= j; i++){
// int x = m - i + 1;
// for(int y = 2 * x; y <= n; y += x){
// merge(x, y);
// }
// }
// if(get_parent(u) == get_parent(v)){
// return true;
// }
// return false;
//}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<vector<pii>> adqry(n + 1);
for(int i = 0; i < q; i++){
int u, v;
cin >> u >> v;
adqry[u].push_back({i, v});
adqry[v].push_back({i, u});
}
vector<int> answer(q, m);
for(int i = 0; i <= n; i++){
par[i] = i;
siz[i] = 1;
}
for(int i = 1; i <= m; i++){
int x = m - i + 1;
for(int y = x; y <= n; y += x){
merge(x, y);
for(pair<int,int> p : adqry[y]){
int id = p.fi;
int z = p.se;
if(get_parent(y) == get_parent(z)){
answer[id] = min(answer[id], i);
}
}
}
}
for(int i = 0; i < q; i++){
cout << answer[i] << "\n";
}
}
