#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
int parent[MAXN], weight[MAXN], depth[MAXN], up[MAXN][20];
vector<int> adj[MAXN];
int find(int i) {
return (parent[i] == i) ? i : (parent[i] = find(parent[i]));
}
void dfs(int u, int p, int d) {
depth[u] = d;
up[u][0] = p;
for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (int v : adj[u]) dfs(v, u, d + 1);
}
int get_lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int i = 19; i >= 0; i--) {
if (depth[u] - (1 << i) >= depth[v]) u = up[u][i];
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
int main() {
int n, m, q;
cin >> n >> m >> q;
iota(parent, parent + 2 * n, 0);
int curr_node = n;
for (int L = m; L >= 1; L--) {
int day = m - L + 1;
for (int j = 2 * L; j <= n; j += L) {
int root_u = find(j - L), root_v = find(j);
if (root_u != root_v) {
curr_node++;
weight[curr_node] = day;
parent[root_u] = parent[root_v] = curr_node;
adj[curr_node].push_back(root_u);
adj[curr_node].push_back(root_v);
}
}
}
for (int i = curr_node; i >= 1; i--) {
if (!depth[i]) dfs(i, i, 1);
}
while (q--) {
int a, b;
cin >> a >> b;
cout << weight[get_lca(a, b)] << "\n";
}
return 0;
}
