#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";
}
}
