#include <bits/stdc++.h>
using namespace std;
// DSU class (provided in the query)
class DSU {
public:
vector<int> parent;
vector<int> size;
int components;
DSU(int n) {
parent.resize(n);
size.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
components = n;
}
int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
if (size[x] < size[y]) {
swap(x, y);
}
parent[y] = x;
size[x] += size[y];
components--;
}
}
bool same(int x, int y) {
return find(x) == find(y);
}
};
vector<pair<int,int>> edges;
vector<int> ans, qs, qe;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
qs.resize(q);
qe.resize(q);
ans.assign(q, 1);
for (int i = 0; i < q; i++) {
cin >> qs[i] >> qe[i]; // Order: x_i, y_i, z_i
qs[i]--, qe[i]--; // Convert to 0-based indexing
}
// Parallel binary search
vector<int> left(q, 1), right(q, m);
bool done = true;
while (done){
done = false;
vector<vector<int>> check_at(m + 1); // Queries to check at each K
for (int i = 0; i < q; i++) {
if (left[i] <= right[i]) {
int mid = (left[i] + right[i]) / 2;
check_at[mid].push_back(i);
done = true;
}
}
DSU dsu(n); // Initialize DSU with N singletons
for (int K = m; K > 0; K--) {
for(int i = K - 1; i + K < n; i += K) {
dsu.unite(i, i + K);
}
for (int i : check_at[K]) {
int x = qs[i], y = qe[i];
if (dsu.same(x, y)) {
left[i] = K + 1;
ans[i] = K;
} else {
right[i] = K - 1;
}
}
}
}
// Output results
for (int i = 0; i < q; i++) {
cout << m - ans[i] + 1 << endl; // Minimal K for each query
}
return 0;
}
