#include <iostream>
#include <sstream>
#include <set>
#include <fstream>
#include <algorithm>
#include <cctype>
#include <iomanip>
#include <vector>
#include <map>
#include <queue>
#include <numeric>
#include <string>
#include <cmath>
#include <climits>
#include <stack>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <bitset>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long ll;
typedef long double ld;
//const int mod = 998244353;
const int mod = 1e9+7;
const int N=5e5+5;
struct DSU {
vector<int> par, sz;
DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }
int find(int x) {
if(x == par[x])return x;
return par[x] = find(par[x]);
}
bool same(int x, int y) { return find(x) == find(y); }
bool join(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (sz[x] < sz[y])
swap(x, y);
sz[x] += sz[y];
par[y] = x;
return true;
}
int size(int x) { return sz[find(x)]; }
};
void solve() {
int n,m,q;
cin>>n>>m>>q;
vector <vector<int>> div(m+1);
for (int i=1;i<=m;i++) {
for (int j=2*i;j<=n;j+=i) div[i].push_back(j);
}
vector <pair<int,int>> quer;
quer.push_back({0,0});
for (int i=1;i<=q;i++) {
int a,b;
cin>>a>>b;
quer.push_back({a,b});
}
vector <int> qe(q+1,m),qs(q+1,1);
bool lessa=true;
while (lessa) {
lessa=false;
vector <vector<int>> mids(m+1);
DSU dsu(n+1);
for (int i=1;i<=q;i++) {
if (qe[i]>=qs[i]) {
mids[(qe[i]+qs[i])>>1].push_back(i);
lessa=true;
}
}
for (int mid=1;mid<=m;mid++) {
for (auto i : div[m-mid+1]) {
dsu.join(m-mid+1,i);
}
for (auto j : mids[mid]) {
if (dsu.same(quer[j].first,quer[j].second)) {
qe[j]=mid-1;
} else {
qs[j]=mid+1;
}
}
}
}
for (int i=1;i<=q;i++) {
if (qe[i]==m) cout<<"-1\n";
else cout<<qe[i]+1<<'\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while (t--) {
solve();
}
return 0;
}
