#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
ll p[100005], siz[100005], ranking[100005];
void reset(ll n)
{
ll i;
for(i = 1; i <= n; i++)
{
p[i] = i;
siz[i] = 1;
ranking[i] = 0;
}
}
ll parent(ll v)
{
if(p[v] == v)
{
return v;
}
return p[v] = parent(p[v]);
}
void merge(ll u, ll v)
{
ll x = parent(u);
ll y = parent(v);
if(x == y)
{
return;
}
if(ranking[x] > ranking[y])
{
p[y] = x;
siz[x] += siz[y];
}
else
{
p[x] = y;
siz[y] += siz[x];
if(ranking[x] == ranking[y])
{
ranking[y]++;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t = 1;
//cin >> t;
while(t--)
{
ll n, m, q;
cin >> n >> m >> q;
ll a[q + 1], b[q + 1], l[q + 1], r[q + 1], i;
for(i = 1; i <= q; i++)
{
cin >> a[i] >> b[i];
l[i] = 1;
r[i] = m;
}
reset(n);
vector<ll>cand[m + 1];
while(true)
{
//cout << "?" << endl;
bool ischange = false;
for(i = 1; i <= q; i++)
{
if(l[i] != r[i])
{
ischange = true;
//cout << i << " " << l[i] << " " << r[i] << endl;
ll mid = (l[i] + r[i]) / 2;
cand[mid].push_back(i);
}
}
if(ischange == false)
{
break;
}
for(i = 1; i <= m; i++)
{
ll j;
ll rielval = m - i + 1;
//cout << rielval << endl;
for(j = rielval * 2; j <= n; j += rielval)
{
merge(rielval, j);
}
if(cand[i].size() == 0)
{
continue;
}
while(cand[i].size() != 0)
{
ll idx = cand[i].back();
//cout << i << " " << idx << endl;
cand[i].pop_back();
ll x = parent(a[idx]), y = parent(b[idx]);
if(x == y)
{
r[idx] = i;
}
else
{
l[idx] = i + 1;
}
}
}
reset(n);
}
for(i = 1; i <= q; i++)
{
cout << r[i] << endl;
}
cout << endl;
}
#ifndef ONLINE_JUDGE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
// Author: tryharderforioi100
