#include <bits/stdc++.h>
#include <random>
#include <chrono>
#define ll long long
#define db double
#define sti string
#define vt vector
#define INF ((int) 1e9)
#define MOD 1000000007
#define BASE 311
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pdd pair<db, db>
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << " = " << x << '\n';
#define bit(mask, i) ((mask >> i) & 1)
#define fi first
#define sc second
using namespace std;
const sti name = "";
const int MAXN = 1e6;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline void file () {
freopen ((name + ".inp").c_str (), "r", stdin);
freopen ((name + ".out").c_str (), "w", stdout);
}
struct DSU {
vt<int> par, sz;
DSU () = default;
DSU (int n) : par (n), sz (n) {
init();
}
void init () {
iota(all(par), 0);
fill(all(sz), 1);
}
int find (int u) {
return u == par[u] ? u : par[u] = find (par[u]);
}
bool unite (int u, int v) {
u = find (u);
v = find (v);
if (u == v) return false;
if (sz[u] < sz[v]) swap (u, v);
par[v] = u;
sz[u] += sz[v];
sz[v] = 0;
return true;
}
};
int main () {
ios_base::sync_with_stdio (false);
cin.tie (nullptr); cout.tie (nullptr);
int n, m, q; cin >> n >> m >> q;
vt<pii> queries(q);
vt<int> left(q, 1), right(q, m);
for (auto& Q : queries)
cin >> Q.fi >> Q.sc;
vt<vt<int>> cand;
DSU g(n + 1);
while (true) {
cand.assign(m + 1, vt<int>());
g.init();
bool any = false;
for (int i = 0; i < q; ++i) {
if (left[i] >= right[i]) continue;
int mid = (left[i] + right[i]) >> 1;
cand[mid].emplace_back(i);
any = true;
}
if (!any) break;
for (int mid = 1; mid <= m; ++mid) {
int step = m - mid + 1;
for (int i = 2 * step; i <= n; i += step)
g.unite(i, i - step);
for (int& i : cand[mid]) {
auto& [u, v] = queries[i];
if (g.find(u) == g.find(v)) right[i] = mid;
else left[i] = mid + 1;
}
}
}
for (int& l : left) cout << l << '\n';
return 0;
}
