#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define vpl vector<pair<long long, long long>>
#define _fastio ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lmax LONG_LONG_MAX
#define lmin LONG_LONG_MIN
#define mxn 200007
#define endl <<'\n'
// #pragma GCC target("sse4")
// #pragma GCC target ("sse4.2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize("03")
// #pragma GCC optimize("unroll loops")
ll t, n, m, k, w;
string s, s1;
const int mod = 1e9 + 7;
vector<vll> reTree;
vector <int> ans;
struct RT
{
int n; // size of the reTree, (V + E)
vector <int> par;
RT (int n) : n(n)
{
par = ans = vector <int>(n + 1);
reTree = vector <vll>(n + 1);
iota(par.begin(), par.end(), 0);
}
inline int find(int x)
{
if (par[x] == x)
return x;
return par[x] = find(par[x]);
}
void build()
{ //{w, u, v} 1 based
// sort(e.begin(), e.end());
int id = n / 2;
for (int i = m; i >= 1; i--)
{
for (ll z = i; z <= n / 2; z += i)
{
int u = i, v = z;
u = find(u), v = find(v);
if (u == v)
{
continue;
}
par[u] = par[v] = ++id;
ans[id] = m - i + 1;
w = id;
reTree[id].push_back(u);
reTree[id].push_back(v);
}
}
}
};
const int LG = 20, N = 2e5 + 7;
int par[N][21], dep[N], sz[N];
void dfs (int u, int p = 0)
{
par[u][0] = p;
dep[u] = 1 + dep[p];
sz[u] = 1;
for (int i = 1; i <= LG; i++)
{
par[u][i] = par[par[u][i - 1]][i - 1];
}
for (auto &&v : reTree[u])
{
if (v == p)
{
continue;
}
dfs(v, u);
sz[u] += sz[v];
}
}
int lca (int u, int v)
{
if (dep[u] < dep[v])
{
swap(u, v);
}
for (int k = LG - 1; k >= 0; k--)
{
if (dep[par[u][k]] >= dep[v])
{
u = par[u][k];
}
}
if (u == v)
{
return u;
}
for (int k = LG - 1; k >= 0; k--)
{
if (par[u][k] != par[v][k])
{
u = par[u][k];
v = par[v][k];
}
}
return par[u][0];
}
signed main()
{
_fastio;
ll tc = 0;
// cin >> t;
// while (t--)
// {
cin >> n >> m >> k;
RT rt(2 * n);
rt.build();
dfs(w);
while (k--)
{
ll u, v;
cin >> u >> v;
ll lc = lca(u, v);
cout << ans[lc] << '\n';
}
// }
return 0;
}
