#include <bits/stdc++.h>
// you just try again
using namespace std;
#define ll long long
void read() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}
const int N = 1e5 + 5;
class DSU {
public:
vector<int> parent, sz;
DSU(int n) {
parent = sz = vector<int>(n);
for (int i = 0; i < n; ++i) {
parent[i] = i, sz[i] = 1;
}
}
int find(int n) {
if (parent[n] == n)return n;
return parent[n] = find(parent[n]);
}
void uni(int x, int y) {
x = find(x), y = find(y);
if (x == y)return;
if (sz[y] > sz[x])swap(x, y);
parent[y] = x, sz[x] += sz[y];
}
bool issame(int x, int y) {
return find(x) == find(y);
}
};
int n, m, q, ql[N], qr[N], u[N], v[N], ans[N];
void code() {
cin >> n >> m >> q;
for (int i = 0; i < q; ++i) {
cin >> u[i] >> v[i];
ql[i] = 1, qr[i] = m;
}
bool lassa = 1;
while (lassa) {
lassa = 0;
vector<vector<int>> mids(m + 1);
DSU dsu(n + 1);
for (int i = 0; i < q; ++i) {
if (ql[i] <= qr[i]) {
lassa = 1;
mids[(ql[i] + qr[i]) >> 1].push_back(i);
}
}
for (int mid = 1; mid <= m; ++mid) {
int val = m - mid + 1;
for (int i = val + val; i <= n; i += val)
if (i <= n)dsu.uni(val, i);
for (auto i: mids[mid]) {
if (dsu.issame(u[i], v[i])) {
ans[i] = mid, qr[i] = mid - 1;
} else {
ql[i] = mid + 1;
}
}
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
}
int main() {
read();
int t = 1;
// cin >> t;
while (t--)
code();
}
