#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define ull unsigned long long
#define int long long
#define pb push_back
#define pf push_front
#define inpt freopen("input.txt", "r", stdin)
#define outpt freopen("output.txt", "w", stdout)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define EPS 1e-6
#define PI acos(-1)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> OrderedSet;
int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
int dy[8] = {1, 0, 0, -1, 1, -1, 1, -1};
const int N = 3e5 + 10, MOD = 998244353, INF = 3e15, LOG = 23, SQ = 320; // SQ = 317 for 1e5, 448 for 2e5
class DSU {
private:
vector<int> Set, sz;
public:
DSU(int n) : Set(n + 1), sz(n + 1, 1) {
for(int i = 1; i <= n; i++) Set[i] = i;
}
int find(int x) { return Set[x] == x ? x : (Set[x] = find(Set[x])); }
int get_size(int x) { return sz[find(x)]; }
void unite(int u, int v) {
u = find(u);
v = find(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
Set[v] = u;
}
bool connected(int x, int y) { return find(x) == find(y); }
};
struct query {
int u, v;
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<query> queries(q + 1);
for(int i = 1; i <= q; i++) cin >> queries[i].u >> queries[i].v;
int l[q + 1], r[q + 1];
for(int i = 1; i <= q; i++) l[i] = 1, r[i] = m;
vector<int> ans(q + 1, INF);
while(true) {
bool ok = false;
vector<int> qry[m + 1];
for(int i = 1; i <= q; i++) {
if(l[i] > r[i]) continue;
ok = true;
qry[l[i] + (r[i] - l[i]) / 2].push_back(i);
}
if(!ok) break;
DSU dsu(n);
for(int i = 1; i <= m; i++) {
for(int j = m - i + 1; j <= n; j += m - i + 1) dsu.unite(m - i + 1, j);
for(auto x : qry[i]) {
if(dsu.connected(queries[x].u, queries[x].v)) {
ans[x] = min(ans[x], i);
r[x] = i - 1;
}
else l[x] = i + 1;
}
}
}
for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}
