#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define lsb(x) (x) & (-x)
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template <typename T>
void print(T t) {
cout << t << "\n";
}
template <typename T, typename... Args>
void print(T t, Args ...args) {
cout << t << " ";
print(args...);
}
const int N = 1e5 + 1;
int n, m, q, ci, ans[N];
struct Query {
int a, b, i;
};
vector <Query> qry;
struct Dsu {
int cnt[N];
int par[N];
vector <pair <pii, pii>> updates;
void unite(int u, int v) {
u = root(u);
v = root(v);
if (u == v) {
updates.pb({{u, v}, {cnt[u], par[v]}});
return;
}
if (cnt[u] < cnt[v]) {
swap(u, v);
}
updates.pb({{u, v}, {cnt[u], par[v]}});
cnt[u] += cnt[v];
par[v] = u;
}
int root(int u) {
return par[u] == u? u: root(par[u]);
}
void rollback() {
auto p = updates.back();
updates.pop_back();
cnt[p.xx.xx] = p.yy.xx;
par[p.xx.yy] = p.yy.yy;
}
} dsu;
void add() {
int i = ++ci;
int x = m - i + 1;
for (int i = x; i <= n; i += x) {
dsu.unite(x, i);
}
}
void rem() {
int i = ci--;
int x = m - i + 1;
for (int i = x; i <= n; i += x) {
dsu.rollback();
}
}
void bin_search(int l, int r, vector <Query> &qry) {
if (l == r) {
for (auto p: qry) {
ans[p.i] = l;
}
return;
}
vector <Query> lef, rig;
int mid = l + r >> 1;
while (ci < mid) add();
while (ci > mid) rem();
for (auto &p: qry) {
if (dsu.root(p.a) == dsu.root(p.b)) {
lef.pb(p);
} else {
rig.pb(p);
}
}
bin_search(l, mid, lef);
bin_search(mid + 1, r, rig);
}
int main() {
ios_base::sync_with_stdio(false);
cin >> n >> m >> q;
for (int i = 0; i < q; ++i) {
int a, b;
cin >> a >> b;
qry.pb({a, b, i});
}
for (int i = 1; i <= n; ++i) {
dsu.cnt[i] = 1;
dsu.par[i] = i;
}
bin_search(0, m, qry);
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
}
