#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template <typename T, typename R> using o_map = tree<T, R, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// #define int long long
// #pragma once
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
typedef long long ll;
#define ld long double
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const int N = 200005, M = 317;
// const int inf = 1e18 + 7;
const ld pi = acos(-1);
// const ll inf = 1e9 + 5;
int n, ara[N];
vector<int> parent(N);
vector<int> adj[N];
vector<int> tin(N), tout(N);
int timer = 0;
vector<vector<int>> up(N, vector<int> (21));
void make_set(int v)
{
parent[v] = v;
}
int find_set(int v){
if(parent[v]==v) return v;
return parent[v] = find_set(parent[v]);
}
void union_set(int u, int v, int val)
{
int up = find_set(u);
int vp = find_set(v);
if(up == vp){
++n;
adj[n].push_back(up);
make_set(n);
parent[up] = n;
ara[n] = val;
}
else{
++n;
adj[n].push_back(up);
adj[n].push_back(vp);
make_set(n);
parent[up] = parent[vp] = n;
ara[n] = val;
}
}
void dfs(int v, int p)
{
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i <= 20; ++i)
if(up[v][i-1] != 0) up[v][i] = up[up[v][i-1]][i-1];
else up[v][i] = 0;
for (int u : adj[v]) {
if (u != p)
dfs(u, v);
}
tout[v] = ++timer;
}
bool is_ancestor(int u, int v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v)
{
if (is_ancestor(u, v))
return u;
if (is_ancestor(v, u))
return v;
for (int i = 20; i >= 0; --i) {
if (!is_ancestor(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
int32_t main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
// cin >> tt;
for(int tc=1; tc<=tt; tc++){
// cout << "Case " << tc << ": ";
int m, q;
cin >> n >> m >> q;
int fn = n;
for(int i=1; i<=n; i++) make_set(i);
for(int i=m; i>=1; i--){
for(int j=2*i; j<=fn; j+=i){
if(find_set(i) != find_set(j)) union_set(i, j, i);
}
}
dfs(n, n);
while(q--){
int a, b;
cin >> a >> b;
int lc = lca(a, b);
cout << m - ara[lc] + 1 << "\n";
}
}
return 0;
}
