#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
int n, m, q;
pii queries[N], gran[N], gran2[N];
vector <int> v[N], vn[N]; //za svaki mid unutra je par <index, <lo, hi> >
vector <pii> dan[N];
int P[N], sol[N];
int name(int x) {
if (x==P[x]) return x;
P[x]=name(P[x]);
return P[x];
}
void mrg(int x, int y) {
x=name(x); y=name(y);
if (x==y) return;
P[x]=y;
}
void load() {
scanf("%d %d %d", &n, &m, &q);
for (int i=0; i<q; ++i) {
int a, b;
scanf("%d %d", &a, &b);
queries[i]=mp(a, b);
v[m/2].pb(i);
gran[m/2]=mp(1, m-1);
}
}
void solve() {
for (int i=2; i<=m; ++i) {
for (int j=i*2; j<=n; j+=i) {
dan[m-i+1].pb(mp(i, j));
//printf("\n");
}
}
// for (int i=1; i<m; ++i) {
// printf("dan == %d: ", i);
// for (pii p:dan[i]) printf("<%d, %d> ", p.X, p.Y);
// printf("\n");
// }
while (1) {
int cnt=0;
for (int i=1; i<=n; ++i) P[i]=i;
for (int i=1; i<m; ++i) {
for (pii pp:dan[i]) mrg(pp.X, pp.Y);
for (int p:v[i]) {
int x=queries[p].X, y=queries[p].Y;
//printf("mid == %d, query: <%d, %d>, lo == %d, hi == %d\n", i, x, y, gran[i].X, gran[i].Y);
int lo, hi, mid;
if (name(x)==name(y)) {
lo=gran[i].X; hi=i;
}
else {
lo=i+1; hi=gran[i].Y;
}
//printf("novi lo == %d, hi == %d\n", lo, hi);
//system("pause");
mid=(lo+hi)/2;
gran2[mid]=mp(lo, hi);
if (lo==hi) {
sol[p]=lo;
}
else {
vn[mid].pb(p);
++cnt;
}
}
v[i].clear();
}
if (cnt==0) break;
for (int i=1; i<m; ++i) {
gran[i]=gran2[i];
for (int pp:vn[i]) v[i].pb(pp);
vn[i].clear();
}
}
for (int i=0; i<q; ++i) {
if (sol[i]==m-1) {
if (name(queries[i].X)==name(queries[i].Y)) printf("%d\n", m-1);
else printf("%d\n", m);
}
else printf("%d\n", sol[i]);
}
}
int main() {
load();
solve();
return 0;
}
