#include <stdio.h>
#define N 333333
int n, m, q,
dfn[N], dep[N], timer, pa[N], k, c[N][2], w[N], now, sz[N], hld[N], Pa[N];
int f(int x) {
if (pa[x] == x)
return x;
return pa[x] = f(pa[x]);
}
void edge(int u, int v) {
u = f(u), v = f(v);
if (u == v) return;
++k;
w[k] = now;
c[k][0] = u;
c[k][1] = v;
Pa[u] = Pa[v] = k;
pa[u] = pa[v] = k;
}
int dfs(int u) {
return ! u ? 0 : sz[u] = 1 + dfs(c[u][0]) + dfs(c[u][1]);;
}
void dfs2(int u, int hd) {
if (! u) return;
dep[u] = dep[Pa[u]] + 1;
dfn[u] = ++timer;
hld[u] = hd;
int d = sz[c[u][1]] >= sz[c[u][0]];
dfs2(c[u][d], hd);
dfs2(c[u][!d], c[u][!d]);
}
int lca(int u, int v) {
while (hld[u] != hld[v]) {
if (dep[hld[u]] < dep[hld[v]])
v = Pa[hld[v]];
else
u = Pa[hld[u]];
}
return dep[u] < dep[v] ? u : v;
}
int main() {
for (int i = 0; i < N; ++i) {
pa[i] = i;
sz[i] = 1;
Pa[i] = i;
}
scanf("%d%d%d", &n, &m, &q);
k = n;
for (int gc = m; gc >= 1; --gc) {
++now;
for (int j = gc; j + gc <= n; j += gc)
edge(j, j + gc);
}
dfs(k);
dfs2(k, k);
for (int aa, bb, i = 0; i < q; ++i) {
scanf("%d%d", &aa, &bb);
printf("%d\n", w[lca(aa, bb)]);
}
return 0;
}
