#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> ii;
void print() {cerr << '\n';} template <typename T, typename... Args>
void print(const T &a, const Args &...args) { cerr << a << ' ', print(args...); }
const int N = 2e5 + 5;
int n, m, q, par[N], w[N], sz[N];
int anc(int u)
{
return u == par[u] ? u : anc(par[u]);
}
void join(int u, int v, int weight)
{
u = anc(u), v = anc(v);
if (u == v) return;
if(sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
w[u] = weight;
}
int Getmax(int u, int v)
{
int ans = 0;
while (u != v)
{
if (w[u] > w[v]) swap(u, v);
ans = w[u];
u = par[u];
}
return ans;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for(int i = 1; i <= n; i++) sz[i] = 1, par[i] = i, w[i] = 1e9;
for(int i = m; i >= 1; i--)
{
for(int j = i; j <= n; j += i)
join(i, j, m - i + 1);
}
while(q--)
{
int u, v;
cin >> u >> v;
cout << Getmax(u, v) << '\n';
}
return 0;
}
/*
nhận xét tất cả các đỉnh có gcd bằng M nối với nhau đồng nghĩa với việc tất cả các đỉnh chia hết cho M đểu thuộc
cùng một thành phần liên thông
*/
