#include <bits/stdc++.h>
using namespace std;
#define int long long
#define i64 long long
/*
* الاستمرارية تصنع الكمال *
* Remember why cp, you aren't Kuhn to match problems with topics.
* If you stuck in problem read it again, if not try to find pattern or solve simple cases.
*/
template <typename T> class SparseTable {
private:
int n, log2dist;
vector<vector<T>> st;
public:
SparseTable(const vector<T> &v) {
n = (int)v.size();
log2dist = 1 + (int)log2(n);
st.resize(log2dist);
st[0] = v;
for (int i = 1; i < log2dist; i++) {
st[i].resize(n - (1 << i) + 1);
for (int j = 0; j + (1 << i) <= n; j++) {
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
}
/** @return minimum on the range [l, r] */
T query(int l, int r) {
int i = (int)log2(r - l + 1);
return min(st[i][l], st[i][r - (1 << i) + 1]);
}
};
class LCA {
private:
const int n;
const vector<vector<int>> &adj;
SparseTable<pair<int, int>> rmq;
vector<int> tin, et, dep;
int timer = 0;
/** prepares tin, et, dep arrays */
void dfs(int u, int p) {
tin[u] = timer;
et[timer++] = u;
for (int v : adj[u]) {
if (v == p) { continue; }
dep[v] = dep[u] + 1;
dfs(v, u);
et[timer++] = u;
}
}
public:
// make sure the adjacency list is 0 indexed
LCA(vector<vector<int>> &_adj, int root)
: n((int)_adj.size()), adj(_adj), tin(n), et(2 * n), dep(n),
rmq(vector<pair<int, int>>(1)) {
dfs(root, -1);
vector<pair<int, int>> arr(2 * n);
for (int i = 0; i < 2 * n; i++) { arr[i] = {dep[et[i]], et[i]}; }
rmq = SparseTable<pair<int, int>>(arr);
}
/** @return LCA of nodes a and b */
int query(int a, int b) {
if (tin[a] > tin[b]) { swap(a, b); }
return rmq.query(tin[a], tin[b]).second;
}
};
void solve() {
int n, m, q ; cin >> n >> m >> q ;
int N = 2*n - 1;
vector<int>par(N), id(N) ;
iota(begin(par), end(par), 0) ;
function<int(int)> find = [&](int u) {
return par[u] == u ? u : par[u] = find(par[u]);
};
int cur = n ;
vector<vector<int>>g(N) ;
auto unit = [&](int u, int v, int t) {
int pu = find(u), pv = find(v);
if (pu == pv) return ;
par[pu] = cur ;
par[pv] = cur ;
g[pu].push_back(cur) ;
g[pv].push_back(cur) ;
g[cur].push_back(pu) ;
g[cur].push_back(pv) ;
id[cur ++] = t ;
};
for (int i = 0 ; i < m ; i ++) {
int gc = m - i ;
for (int j = gc ; j <= n ; j += gc) {
unit(gc - 1, j - 1, i + 1) ;
}
}
LCA l(g, cur - 1) ;
while (q--) {
int u, v ; cin >> u >> v ;
u -- ; v-- ;
cout << id[l.query(u, v)] << '\n' ;
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
clock_t start = clock();
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
int tc = 1;
// cin >> tc;
for (int ttt = 1; ttt <= tc; ttt++) {
#ifdef LOCAL
cout << "Case " << ttt << ": ";
#endif
solve();
}
#ifdef LOCAL
clock_t end = clock();
double time_taken = double(end - start) / CLOCKS_PER_SEC;
cout << "\n\n\n\n\nTime taken: " << time_taken << " seconds\n";
#endif
return 0 ;
}
