#include <bits/stdc++.h>
using namespace std;
#define _DEBUG 0
struct Tree {
int n, root;
vector <vector<int>> adj;
vector <int> in, out, head, par, h, s;
vector <int> euler;
Tree(int n, vector<vector<int>> adj, int root) : n(n), adj(adj), root(root), in(n), out(n),
h(n), head(n), par(n), s(n), euler() {
auto dfs = [&](auto dfs, int u, int p, int depth = 0) -> void {
h[u] = depth;
par[u] = p;
s[u] = 1;
for (int v : adj[u])
if (v != p) {
dfs(dfs, v, u, depth + 1);
s[u] += s[v];
}
};
dfs(dfs, root, root);
auto build = [&](auto self, int u, int p, int _head) -> void {
in[u] = euler.size();
euler.push_back(u);
head[u] = _head;
int it = -1;
for (int v : adj[u])
if (v != p)
if (it == -1 || s[it] < s[v]) it = v;
if (it != -1)
self(self, it, u, _head);
for (int v : adj[u])
if (v != p && v != it) {
self(self, v, u, v);
}
out[u] = euler.size();
};
build(build, root, root, root);
}
int lca(int u, int v) {
while (head[u] != head[v]) {
if (h[head[u]] > h[head[v]]) swap(u, v);
v = par[head[v]];
}
if (h[u] > h[v]) swap(u, v);
return u;
}
};
template<class Info>
struct SegmentTree {
vector <Info> f;
int n;
SegmentTree(int n, vector <Info> a) : n(n), f(4 * n, Info()) {
auto dfs = [&](auto dfs, int x, int lx, int rx) -> void {
if (lx + 1 == rx) {
f[x] = a[lx];
return;
}
int mid = (lx + rx) / 2;
dfs(dfs, 2*x, lx, mid);
dfs(dfs, 2*x + 1, mid, rx);
pull(x);
};
dfs(dfs, 1, 0, n);
}
void modify(int idx, Info val) {
auto dfs = [&](auto dfs, int x, int lx, int rx) -> void {
if (lx + 1 == rx) {
f[x] = val;
return;
}
int mid = (lx + rx) / 2;
if (idx < mid)
dfs(dfs, 2*x, lx, mid);
else
dfs(dfs, 2*x + 1, mid, rx);
pull(x);
};
dfs(dfs, 1, 0, n);
}
Info rangeQuery(int l, int r) {
auto dfs = [&](auto dfs, int x, int lx, int rx) -> Info {
if (lx >= r || rx <= l) return Info();
if (lx >= l && rx <= r) return f[x];
int mid = (lx + rx) / 2;
return dfs(dfs, 2*x, lx, mid) + dfs(dfs, 2*x + 1, mid, rx);
};
return dfs(dfs, 1, 0, n);
}
void pull(int x) {
f[x] = f[2*x] + f[2*x+1];
}
SegmentTree(int n) {
SegmentTree(n, vector<Info>(n, Info()));
}
};
struct Info {
array<int, 2> mx = {0, 0};
Info() {}
Info(int x, int y) : mx({x, y}) {}
Info operator+(const Info &b) {
Info z;
z.mx = max(mx, b.mx);
return z;
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n, m, q; cin >> n >> m >> q;
vector <tuple<int, int, int>> e;
for (int i = m; i >= 1; i--) {
for (int j = i + i; j <= n; j += i) {
if (_DEBUG) cout << j-1 << ',' << j-i-1 << ',' << m-i << '\n';
e.push_back({j - 1, j - i - 1, m - i});
}
}
{ /// DSU tree
vector <vector <int>> adj(n);
vector <int> p(n), t(n, -1); iota(p.begin(), p.end(), 0);
int root = 0;
{
auto regis = [&](int w = -1) -> int {
int sz = p.size();
p.push_back(sz);
adj.push_back(vector<int>());
t.push_back(w);
return p.size() - 1;
};
auto addedge = [&](int u, int v) -> void {
adj[u].push_back(v);
adj[v].push_back(u);
};
auto get = [&](auto self, int u) -> int {
return p[u] = (p[u] == u) ? u : self(self, p[u]);
};
auto U = [&](int u, int v, int time) -> void {
u = get(get, u), v = get(get, v);
if (u == v) return ;
int x = regis(time);
addedge(x, u);
addedge(x, v);
p[u] = p[v] = x;
if (_DEBUG) cout << u << " & " << v << " --> " << x << " " << t[x] << endl;
root = x;
};
for (auto [u, v, w] : e)
U(u, v, w);
vector <int> rts;
for (int i = 0; i < p.size(); i++) {
if (i == get(get, i)) rts.push_back(i);
}
if (rts.size() > 1) {
for (int i = 1; i < rts.size(); i++)
U(rts[i-1], rts[i], 2);
}
}
Tree tree(p.size(), adj, root);
for (int i = 0; i < q; i++) {
int u, v; cin >> u >> v;
u--; v--;
int x = tree.lca(u, v);
cout << t[x] + 1 << '\n';
}
}
}
