#include <bits/stdc++.h> using namespace std; long long i, j, l, r, mid, p, q, k, t, n, m, a, b, c, d, cnt, res, parent[100005], sz[100005], ans[100005]; const long long mod = 999993143, mod2 = 999993469; string s; bool check; void make_set (long long v){ parent[v] = v; sz[v] = 1; } long long find_set (long long v){ if (v == parent[v]){ return v; } return parent[v] = find_set(parent[v]); } void union_set (long long a, long long b){ a = find_set(a); b = find_set(b); if (a != b){ if (sz[a] < sz[b]){ swap(a, b); } parent[b] = a; sz[a] += sz[b]; } } pair <long long, long long> ed[100005]; struct query{ long long l, r, s1, s2, id; }; query qq[100005]; bool cmp (query a, query b){ long long mid1 = (a.l + a.r) / 2, mid2 = (b.l + b.r) / 2; return mid1 < mid2; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for (i = 1; i <= q; i += 1){ cin >> a >> b; qq[i] = {1, m, a, b, i}; } t = 17; while (t--){ sort(qq + 1, qq + q + 1, cmp); for (i = 1; i <= n; i += 1){ make_set(i); } p = 0; res = m; for (i = 1; i <= q; i += 1){ mid = (qq[i].l + qq[i].r) / 2; while (p <= mid){ for (j = res; j <= n - res; j += res){ union_set(j, j + res); } res -= 1; p += 1; } if (find_set(qq[i].s1) == find_set(qq[i].s2)){ ans[qq[i].id] = mid; qq[i].r = mid - 1; } else{ qq[i].l = mid + 1; } } } for (i = 1; i <= q; i += 1){ cout << ans[i] + 1 << "\n"; } }