#include <bits/stdc++.h>
using namespace std;
#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x) * (x))
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) ((int)(x).size())
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);
using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;
template <typename T>
using heap = priority_queue<T>;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }
// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 1E5 + 5, LG = 18;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 4E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr double EPS = 1E-10;
int n, m, q;
int dsu[2 * N], val[2 * N];
vi adj[2 * N];
int up[2 * N][LG + 1], depth[2 * N];
int cnt = 0;
int find(int u) {
return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}
void add_edge(int u, int v, int t) {
u = find(u); v = find(v);
if (u == v) return;
++cnt;
val[cnt] = t;
dsu[u] = dsu[v] = dsu[cnt] = cnt;
adj[cnt].push_back(u);
adj[cnt].push_back(v);
}
void dfs(int u) {
for (int v : adj[u]) {
up[v][0] = u;
depth[v] = depth[u] + 1;
dfs(v);
}
}
void init_lift() {
FOR(e, 1, LG) {
FOR(i, 1, cnt) {
up[i][e] = up[up[i][e - 1]][e - 1];
}
}
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
FOD(e, LG, 0) {
if (depth[u] - (1 << e) >= depth[v]) {
u = up[u][e];
}
}
if (u == v) return u;
FOD(e, LG, 0) {
if (up[u][e] != up[v][e]) {
u = up[u][e];
v = up[v][e];
}
}
return up[u][0];
}
void solve() {
cin >> n >> m >> q;
cnt = n;
FOR(i, 1, n) {
dsu[i] = i;
}
FOR(i, 1, m) {
int x = m - i + 1;
for (int y = x * 2; y <= n; y += x) {
add_edge(x, y, i);
}
}
dfs(cnt);
init_lift();
while (q--) {
int a, b;
cin >> a >> b;
cout << val[lca(a, b)] << el;
}
}
int main() {
fast_io
#define LOCAL
#ifndef LOCAL
#define PROBLEM ""
freopen(PROBLEM ".INP", "r", stdin);
freopen(PROBLEM ".OUT", "w", stdout);
#endif
int t = 1;
// cin >> t;
while (t--) solve();
}
