#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using ll = long long;
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
/*
* this comment fills you with Determination.
*/
const int N = 1e5 + 7;
int sz[N], par[N];
void init(int n) {
for (int i = 0; i < n; ++i)
par[i] = -1, sz[i] = 0;
}
int parent(int u) {
if (par[u] == -1)
return u;
else
return par[u] = parent(par[u]);
}
bool is_united(int u, int v) {
u = parent(u);
v = parent(v);
return (u == v);
}
bool unite(int u, int v) {
u = parent(u);
v = parent(v);
if (u == v)
return false;
if (sz[u] < sz[v])
swap(u, v);
par[v] = u;
sz[u] += sz[v];
return true;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifdef CAROOT
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int tt = 1;
// cin >> tt;
for (int tc = 1; tc <= tt; ++tc) {
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int>> queries(q);
for (auto &[a, b]: queries)
cin >> a >> b;
vector<int> l(q, 1), r(q, m), ans(q);
bool lessa = true;
while (lessa) {
lessa = false;
vector<vector<int>> mids(m + 1);
for (int i = 0; i < q; ++i) {
if (l[i] <= r[i]) {
lessa = true;
mids[(l[i] + r[i]) / 2].push_back(i);
}
}
init(n + 1);
for (int mid = m; mid > 0; --mid) {
for (int j = mid * 2; j <= n; j += mid)
unite(mid, j);
for (auto i: mids[mid]) {
int a = queries[i].first;
int b = queries[i].second;
if (is_united(a, b))
l[i] = mid + 1, ans[i] = m - mid + 1;
else
r[i] = mid - 1;
}
}
}
for (auto &i : ans)
cout << i << '\n';
cout << '\n';
}
return 0;
}
