#define _USE_MATH_DEFINES
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int dx2[] = {1, -1, 0, 0, -1, 1, -1, 1};
int dy2[] = {0, 0, 1, -1, 1, 1, -1, -1};
int knightX[] = {-2, -2, 2, 2, 1, 1, -1, -1};
int knightY[] = {-1, 1, -1, 1, -2, 2, -2, 2};
const ll INF = 2e18;
const int N = 1e6 + 10, K = 100 + 10, LOG = 20;
const ll MOD = 1e9 + 7;
struct DSU {
vector<ll> f, siz, points;
DSU() {}
DSU(int n) {
init(n + 1);
}
void init(int n) {
f.resize(n);
points.resize(n, 0);
iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int leader(int x) {
if(x == f[x]){
return f[x];
}
return f[x] = leader(f[x]);
}
bool same(int x, int y) {
return leader(x) == leader(y);
}
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) {
return false;
}
if (siz[x] < siz[y]) {
swap(x , y);
}
points[y] -= points[x];
siz[x] += siz[y];
f[y] = x;
return true;
}
void add(int u, ll val){
points[leader(u)] += val;
}
ll get(int u){
if(f[u] == u){
return points[u];
}
return points[u] + get(f[u]);
}
int size(int x) {
return siz[leader(x)];
}
};
int main() {
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// #endif
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) {
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int>> qq(q);
for(auto &[a, b] : qq){
cin >> a >> b;
}
bool ok = true;
vector<int> l(q, 1), r(q, m), ans(q, -1);
while(ok){
ok = false;
vector<vector<int>> have(m + 1);
for(int i = 0; i < q; i++){
if(l[i] <= r[i]){
ok = true;
have[(l[i] + r[i]) >> 1].push_back(i);
}
}
if(!ok){
break;
}
DSU d(n);
for(int mid = 1; mid <= m; mid++){
int st = m - mid + 1;
if(st){
for(int g = 2 * st; g <= n; g += st){
d.merge(st, g);
}
}
for(auto &j : have[mid]){
if(d.same(qq[j].first, qq[j].second)){
r[j] = mid - 1;
ans[j] = mid;
}
else{
l[j] = mid + 1;
}
}
}
}
for(auto &i : ans){
cout << i << endl;
}
}
return 0;
}
