/**
* Author: Lưu Diệp Thành (Save Diệp Thành)
* Le Hong Phong High School for the Gifted (i2528)
**/
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define ll long long
#define ushort unsigned short
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORN(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define endl '\n'
#define sz(x) (int)x.size()
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define ins insert
#define segleft (id<<1)
#define segright (id<<1|1)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
const int MOD = 1e9+7;
struct info {
int a,b;
};
struct DSU {
vector<int> par, num;
int n;
DSU() {}
void init(int _n) {
n = _n;
par.assign(n+5, 0);
num.assign(n+5, 0);
iota(all(par), 0);
fill(all(num), 1);
}
int findpar(int u) {
return (par[u] == u ? u : par[u] = findpar(par[u]));
}
bool unite(int u, int v) {
u = findpar(u);
v = findpar(v);
if (u==v) return false;
if (num[u] < num[v]) swap(u,v);
par[v] = u;
num[u] += num[v];
return true;
}
};
const int N = 1e5+5;
vector<info> query(N);
vector<int> canMid[N];
int n,q,m;
void Semicolon() {
cin >> n >> m >> q;
FOR(i, 1, q) {
cin >> query[i].a >> query[i].b;
}
vector<int> l(q+5,1), r(q+5,m), ans(q+5);
bool flag = true;
DSU dsu;
dsu.init(n);
FOR(i, 1, q) {
if (query[i].a==query[i].b) {
l[i] = m+1;
r[i] = 0;
ans[i] = 0;
}
}
while(flag) {
flag = false;
FOR(i, 1, q) {
if (l[i] > r[i]) continue;
int mid = (l[i] + r[i])>>1;
flag = true;
canMid[mid].pb(i);
}
if (!flag) break;
FOR(day, 1, m) {
int t = m-day+1;
for(int j = 2*t; j <= n; j+=t) {
dsu.unite(j, j - t);
}
for(int index : canMid[day]) {
auto[a,b] = query[index];
if (dsu.findpar(a) == dsu.findpar(b)) {
ans[index] = day;
r[index] = day-1;
} else {
l[index] = day+1;
}
}
vector<int>().swap(canMid[day]);
}
dsu.init(n);
}
FOR(i, 1, q) {
cout << ans[i] << endl;
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("", "r", stdin);
//freopen("", "w", stdout);
if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
int t = 1;
//cin >> t;
while(t--) Semicolon();
cerr << endl;
cerr << "Time elapsed: " << TIME << " s.\n ";
return (0 ^ 0);
}
