#include <bits/stdc++.h>
using namespace std;
int parent[100001], ranc[100001], height[100001];
pair<int,int> binjump[100001][20];
int find (int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void join(int x, int y) {
int px = find(x), py = find(y);
if (ranc[px] > ranc[py]) {
parent[py] = px;
} else if (ranc[px] < ranc[py]) {
parent[px] = py;
} else {
parent[py] = px;
ranc[px]++;
}
}
int maxpath(int a, int b) {
if (height[a] < height[b]) {
swap(a, b);
}
int diffh = height[a] - height[b], ans = -1;
for (int i=0;i<20;i++) {
if ((diffh>>i) & 1) {
ans = max(ans, binjump[a][i].second);
a = binjump[a][i].first;
}
}
if (a == b) {
return ans;
}
for (int i=19;i>-1;i--) {
//cout << binjump[a][i].first << ' ' << binjump[b][i].first << '\n';
if (binjump[a][i].first != binjump[b][i].first) {
ans = max(ans, binjump[a][i].second);
ans = max(ans, binjump[b][i].second);
a = binjump[a][i].first;
b = binjump[b][i].first;
}
}
ans = max(ans, binjump[a][0].second);
ans = max(ans, binjump[b][0].second);
return ans;
}
int main() {
for (int i=0;i<100001;i++) {
parent[i] = i;
ranc[i] = 1;
height[i] = -1;
for (int j=0;j<20;j++) {
binjump[i][j] = make_pair(-1, -1);
}
}
int n, m, q; cin >> n >> m >> q;
vector<vector<pair<int,int>>> tree(n+1);
for (int i=m;i>0;i--) {
for (int j=2*i;j<n+1;j+=i) {
if (find(j - i) != find(j)) {
join(j - i, j);
tree[j - i].push_back(make_pair(j, m - i + 1));
tree[j].push_back(make_pair(j - i, m - i + 1));
}
}
}
stack<pair<int,int>> stac; stac.push(make_pair(1, 0));
pair<int,int> curpair;
parent[1] = 0;
binjump[1][0] = make_pair(1, 0);
while (stac.size() > 0) {
curpair = stac.top(); stac.pop();
height[curpair.first] = curpair.second;
for (pair<int,int> i: tree[curpair.first]) {
if (height[i.first] == -1) {
stac.push(make_pair(i.first, curpair.second + 1));
binjump[i.first][0] = make_pair(curpair.first, i.second);
}
}
}
int ahead;
for (int j=1;j<20;j++) {
for (int i=1;i<n+1;i++) {
ahead = binjump[i][j - 1].first;
binjump[i][j] = make_pair(binjump[ahead][j-1].first, max(binjump[i][j-1].second, binjump[ahead][j-1].second));
}
}
/*
for (int i=1;i<n+1;i++) {
cout << i << " : ";
for (pair<int,int> j: tree[i]) {
cout << '(' << j.first << ' ' << j.second << ") ";
}
cout << '\n';
}
for (int i=1;i<n+1;i++) {
cout << i << " : ";
for (int j=0;j<6;j++) {
cout << '(' << binjump[i][j].first << ' ' << binjump[i][j].second << ") ";
}
cout << '\n';
}
*/
vector<int> ansvec;
int query1, query2;
for (int i=0;i<q;i++) {
cin >> query1 >> query2;
ansvec.push_back(maxpath(query1, query2));
}
for (int i: ansvec) {
cout << i << '\n';
}
}
