#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
struct DSU {
vector<int> par, rank, setsize;
int numsets;
explicit DSU(int n) {
par.assign(n, 0);
iota(begin(par), end(par), 0);
rank.assign(n, 0);
setsize.assign(n, 1);
numsets = n;
}
void reset() {
iota(begin(par), end(par), 0);
fill(begin(rank), end(rank), 0);
fill(begin(setsize), end(setsize), 0);
}
int findSet(int x) { return (par[x] == x) ? x : (par[x] = findSet(par[x])); }
bool sameSet(int x, int y) { return findSet(x) == findSet(y); }
bool unite(int x, int y) {
if (sameSet(x, y)) return false;
x = findSet(x), y = findSet(y);
if (rank[x] > rank[y]) swap(x, y);
par[x] = y;
if (rank[x] == rank[y]) ++rank[y];
setsize[y] += setsize[x];
--numsets;
return true;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, Q;
cin >> n >> m >> Q;
vector<pair<int, int>> q(Q);
vector<vector<pair<int, pair<int, int>>>> mids(m + 10);
for (int i = 0; i < Q; ++i) {
mids[(1 + m) / 2].emplace_back(i, make_pair(1, m));
}
for (auto &[a, b] : q) cin >> a >> b;
vector<pair<int, int>> bounds(Q, {1, m});
vector<int> sol(Q, -1);
int done = 0;
DSU dsu(n + 10);
while (done < Q) {
vector<vector<pair<int, pair<int, int>>>> nxt(m + 10);
dsu.reset();
for (int i = 1; i <= m; ++i) {
for (int j = 2 * (m - i + 1); j <= n; j += m - i + 1) {
dsu.unite(m - i + 1, j);
}
for (auto [a, bd] : mids[i]) {
int cmid = (bd.F + bd.S) / 2;
if (dsu.sameSet(q[a].F, q[a].S)) {
if (bd.F == bd.S) {
sol[a] = i;
done++;
} else {
nxt[cmid].emplace_back(a, make_pair(bd.F, i));
}
} else {
nxt[cmid].emplace_back(a, make_pair(i + 1, bd.S));
}
}
}
mids = nxt;
}
for (int i = 0; i < Q; ++i) {
cout << sol[i] << '\n';
}
return 0;
}
