#include <bits/stdc++.h>
using namespace std;
#define el '\n'
#define sp ' '
#define all(v) v.begin(), v.end()
#define rall(v) (v).rbegin(), (v).rend()
#define YES cout << "YES\n"
#define Yes cout << "Yes\n"
#define yes cout << "yes\n"
#define NO cout << "NO\n"
#define No cout << "No\n"
#define no cout << "no\n"
#define int long long
#define double long double
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll,ll>
#define loop int t; cin >> t; for(int i=1;i<=t;++i)
#define mms(arr, val) memset(arr, val, sizeof arr)
void PG_Mazen() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
}
const double EPS = 1e-7, PI = acos(-1);
const int N = 1e5 + 5, MOD = 1e9 + 7, oo = 0x3f3f3f3f;
const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int knightX[] = {-2, -2, 2, 2, 1, 1, -1, -1};
const int knightY[] = {-1, 1, -1, 1, -2, 2, -2, 2};
const ll ooo = 0x3f3f3f3f3f3f3f3f;
struct DSU {
vector<int> par, sz;
DSU(int n) {
par = sz = vector<int>(n + 1);
for (int i = 0; i <= n; ++i) {
par[i] = i;
sz[i] = 1;
}
}
int getParent(int x) {
if (par[x] == x)
return x;
return par[x] = getParent(par[x]);
}
bool connect(int u, int v) {
u = getParent(u);
v = getParent(v);
if (u == v)
return false;
if (sz[u] < sz[v])
par[u] = v, sz[v] += sz[u];
else
par[v] = u, sz[u] += sz[v];
return true;
}
bool isConnected(int u, int v) {
return getParent(u) == getParent(v);
}
};
int ql[N], qr[N], ans[N];
void testCase() {
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int>> que(q);
for (int i = 0; i < q; ++i) {
cin >> que[i].first >> que[i].second;
ql[i] = 1;
qr[i] = m;
}
bool all_answered = false;
while (!all_answered) {
all_answered = true;
vector<vector<int>> mids(m + 1);
for (int i = 0; i < q; ++i) {
if (ql[i] <= qr[i]) {
mids[(ql[i] + qr[i]) / 2].push_back(i);
all_answered = false;
}
}
DSU dsu(n + 1);
for (int mid = 1; mid <= m; ++mid) {
int cur = m - mid + 1, lst = cur;
for (int j = cur * 2; j <= n; j += mid) {
dsu.connect(lst, j);
lst = j;
}
for (auto &i: mids[mid]) {
int a = que[i].first, b = que[i].second;
if (dsu.isConnected(a, b))
qr[i] = mid - 1, ans[i] = mid;
else
ql[i] = mid + 1;
}
}
}
for(int i = 0; i < q; ++i)
cout << ans[i]<< el;
}
int32_t main() {
PG_Mazen();
//sieve();
//sieveSPF();
//precompute();
testCase();
//cerr << clock() / 1000.0 << " Secs";
}
