#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 10, LOG = 20;
// build krt
int n, cur_v;
int dsu_pai[MAXN], krt_pai[MAXN], cl[MAXN], cr[MAXN], val[MAXN];
void krt_init() {
for (int i = 1; i <= n; i++) {
dsu_pai[i] = krt_pai[i] = i;
val[i] = cl[i] = cr[i] = 0;
}
cur_v = n;
}
int krt_find(int v) {
if (v == dsu_pai[v]) return v;
return dsu_pai[v] = krt_find(dsu_pai[v]);
}
void krt_merge(int u, int v, int t) {
u = krt_find(u); v = krt_find(v);
if (u == v) return;
cur_v++;
krt_pai[cur_v] = krt_pai[u] = krt_pai[v] = cur_v;
dsu_pai[cur_v] = dsu_pai[u] = dsu_pai[v] = cur_v;
cl[cur_v] = u;
cr[cur_v] = v;
val[cur_v] = t;
}
// build data structures to make queries in the krt
int cur_t;
int dp_lca[LOG][MAXN], depth[MAXN], tin[MAXN];
int dp_rmq[LOG][MAXN];
void dfs(int v, int d) {
if (v == 0) return;
tin[v] = ++cur_t;
depth[v] = d;
dfs(cl[v], d + 1);
dfs(cr[v], d + 1);
}
int lca(int a, int b) {
if (a == b) return a;
if (depth[a] > depth[b]) swap(a, b);
for (int i = LOG - 1; i >= 0; i--) {
int cand = dp_lca[i][b];
if (depth[cand] >= depth[a]) b = cand;
}
if (a == b) return a;
for (int i = LOG - 1; i >= 0; i--) {
int cand_a = dp_lca[i][a];
int cand_b = dp_lca[i][b];
if (cand_a != cand_b) {
a = cand_a;
b = cand_b;
}
}
return krt_pai[a];
}
void ds_build() {
cur_t = 0;
for (int v = 1; v <= cur_v; v++) {
if (krt_pai[v] == v) {
dfs(v, 0);
}
}
for (int v = 1; v <= cur_v; v++) {
dp_lca[0][v] = krt_pai[v];
}
for (int i = 1; i < LOG; i++) {
for (int v = 1; v <= cur_v; v++) {
dp_lca[i][v] = dp_lca[i - 1][dp_lca[i - 1][v]];
}
}
}
// entrypoint
void solve() {
int m, q;
cin >> n >> m >> q;
krt_init();
for (int d = m; d >= 1; d--) {
for (int j = 2 * d; j <= n; j += d) {
krt_merge(d, j, m - d + 1);
}
}
ds_build();
while (q--) {
int l, r; cin >> l >> r;
cout << val[lca(l, r)] << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
while (t--) {
solve();
}
return 0;
}
