#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int nn = 1e5 + 5;
int p[nn], ranke[nn], L[nn], R[nn], ans[nn];
vector<int> query[nn];
struct pasangan {
int c1;
int c2;
};
pasangan arr[nn];
int findSet(int nod) {
if (p[nod] == nod) return nod;
else return p[nod] = findSet(p[nod]);
}
bool cek(int n1, int n2) {
n1 = findSet(n1);
n2 = findSet(n2);
if (n1 == n2) return 1;
else return 0;
}
void gabung(int n1, int n2) {
n1 = findSet(n1);
n2 = findSet(n2);
if (ranke[n1] < ranke[n2]) {
p[n1] = n2;
} else {
p[n2] = n1;
if (ranke[n1] == ranke[n2]) ranke[n1]++;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
for (int i = 1; i <= Q; i++) {
cin >> arr[i].c1 >> arr[i].c2;
L[i] = 1, R[i] = M;
ans[i] = -1;
}
bool iterasi = 1;
while (iterasi) {
iterasi = 0;
for (int i = 1; i <= N; i++) {
p[i] = i;
ranke[i] = 0;
}
for (int i = 1; i <= M; i++) {
query[i].clear();
}
for (int i = 1; i <= Q; i++) {
/*cout << L[i] << ' ' << R[i] << "\n";*/
if (L[i] <= R[i]) {
iterasi = 1;
query[(L[i] + R[i]) >> 1].push_back(i);
}
}
/*cout << "\n";*/
for (int i = 1; i <= M; i++) {
int j = 2;
while (j * (M - i + 1) <= N) {
if (!cek(M - i + 1, j * (M - i + 1)))
gabung(M - i + 1, j * (M - i + 1));
j++;
}
int l1 = query[i].size();
for (j = 0; j < l1; j++) {
int idx = query[i][j];
if (cek(arr[idx].c1, arr[idx].c2)) {
ans[idx] = i;
R[idx] = i - 1;
} else L[idx] = i + 1;
}
}
}
for (int i = 1; i <= Q; i++) {
cout << ans[i] << "\n";
}
}
