#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define lsb(x) (x) & (-x)
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template <typename T>
void print(T t) {
cout << t << "\n";
}
template <typename T, typename... Args>
void print(T t, Args ...args) {
cout << t << " ";
print(args...);
}
const int N = 2e5 + 1;
const int L = 20;
int n, m, q;
struct Graph {
int ind[N];
int dep[N];
int par[N];
int anc[N][L];
vector <int> adj[N];
} g;
struct Dsu {
int par[N];
int cnt[N];
int ind[N];
int root(int u) {
return u == par[u]? u: par[u] = root(par[u]);
}
void unite(int u, int v) {
u = root(u);
v = root(v);
if (u == v) {
return;
}
if (cnt[u] < cnt[v]) {
swap(u, v);
}
cnt[u] += cnt[v];
par[v] = u;
}
} dsu;
void dfs(int u, int d = 0) {
static int t = 0;
g.dep[u] = d;
g.anc[u][0] =
g.par[u];
for (int i = 1; i < L; ++i) {
g.anc[u][i] =
g.anc[g.anc[u][i - 1]][i - 1];
}
for (int v: g.adj[u]) {
g.par[v] = u;
dfs(v, d + 1);
}
}
int lca(int u, int v) {
if (g.dep[u] < g.dep[v]) {
swap(u, v);
}
int k = g.dep[u] - g.dep[v];
for (int i = 0; i < L; ++i) {
if (k >> i & 1) {
u = g.anc[u][i];
}
}
if (u == v) {
return u;
}
for (int i = L - 1; i >= 0; --i) {
if (g.anc[u][i] != g.anc[v][i]) {
u = g.anc[u][i];
v = g.anc[v][i];
}
}
return g.par[u];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) {
dsu.cnt[i] = 1;
dsu.par[i] = i;
dsu.ind[i] = i;
}
int on = n;
for (int i = m; i >= 1; --i) {
for (int j = i; j <= on; j += i) {
if (dsu.root(i) != dsu.root(j)) {
++n;
int u = dsu.ind[dsu.root(i)];
int v = dsu.ind[dsu.root(j)];
g.adj[n].pb(u);
g.adj[n].pb(v);
g.ind[n] = i;
dsu.unite(i, j);
dsu.ind[dsu.root(i)] = n;
}
}
}
dfs(n);
for (int i = 0; i < q; ++i) {
int u, v;
cin >> u >> v;
cout << m - g.ind[lca(u, v)] + 1 << "\n";
}
}
