#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 10;
set<int> v[mxN];
vector<int> point[mxN];
int sz[mxN], par[mxN], query[mxN][2], st[mxN], en[mxN], ans[mxN];
int find(int u){
if(par[u] == u) return u;
return par[u] = find(par[u]);
}
void unite(int u, int v){
u = find(u), v = find(v);
if(u ^ v){
if(sz[u] > sz[v]) sz[u] += sz[v], par[v] = u;
else sz[v] += sz[u], par[u] = v;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i <= m; ++i){
for(int j = i; j <= n; j += i){
if(v[i + 1].find(j) == v[i + 1].end()){
v[i].insert(j);
}
}
}
for(int i = 0; i < q; ++i){
cin >> query[i][0] >> query[i][1];
st[i] = 1, en[i] = m, ans[i] = 1e9;
point[(en[i] + st[i]) / 2].push_back(i);
}
// 3 6
// 2 4,6, 8
for(int i = 0; i < 19; ++i){
for(int j = 1; j <= n; ++j){
par[j] = j, sz[j] = 1;
}
for(int j = m; j >= 1; --j){
int fi = -1;
for(auto k : v[j]){
if(fi != -1) unite(fi, k);
else fi = k;
}
for(auto it : point[j]){
if(find(query[it][0]) == find(query[it][1])){
st[it] = j + 1;
ans[it] = min(ans[it], m - j + 1);
}else{
en[it] = j - 1;
}
}
point[j].clear();
}
for(int j = 0; j < q; ++j){
if(st[j] <= en[j]){
point[(en[j] + st[j]) / 2].push_back(j);
}
}
}
for(int i = 0; i < q; ++i) cout << ans[i] << "\n";
return 0;
}
