#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 1e5 + 10;
int n, m, k, fi[N];
set <int> vis;
vector <int> v[N], queries[N];
struct query {
int x, y, l, r, ans;
} q[N];
struct DSU {
int par[N];
int FindPar(int u) {
return par[u] < 0 ? u : par[u] = FindPar(par[u]);
}
void unite(int x, int y) {
x = FindPar(x);
y = FindPar(y);
if (x == y) return;
if (par[x] > par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
}
void reset() {
for (int i = 1; i <= n; ++i) par[i] = -1;
}
bool same(int x, int y) {
return FindPar(x) == FindPar(y);
}
} dsu;
int main() {
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> m >> k;
for (int i = 1; i <= k; ++i) {
cin >> q[i].x >> q[i].y;
if (q[i].x == q[i].y) {
q[i].ans = 0;
q[i].l = m; q[i].r = -1;
} else {
q[i].l = q[i].ans = 1;
q[i].r = m;
}
}
for (int i = m; i >= 1; --i) {
vis.clear();
for (int j = i; j <= n; j += i) {
if (fi[j] && vis.find(fi[j]) == vis.end()) {
vis.insert(fi[j]);
v[i].push_back(j);
} else {
if (!fi[j]) {
fi[j] = i;
v[i].push_back(j);
}
}
}
}
while (true) {
bool ck = false;
for (int i = 1; i <= k; ++i) {
if (q[i].l > q[i].r) continue;
queries[(q[i].l + q[i].r) >> 1].push_back(i);
ck = true;
}
if (!ck) break;
dsu.reset();
for (int i = m; i >= 1; --i) {
for (int j = 1; j < v[i].size(); ++j) dsu.unite(v[i][j], v[i][j - 1]);
for (int z: queries[i]) {
if (dsu.same(q[z].x, q[z].y)) {
q[z].ans = i;
q[z].l = i + 1;
} else {
q[z].r = i - 1;
}
}
queries[i].clear();
}
}
for (int i = 1; i <= k; ++i) {
if (q[i].ans == 0) cout << "0\n";
else cout << m - q[i].ans + 1 << "\n";
}
return 0;
}
