#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ld long double
#define lld long long double
#define endl "\n"
#define fastio() \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL); \
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x)
{
cerr << '{';
__print(x.first);
cerr << ',';
__print(x.second);
cerr << '}';
}
template <typename T>
void __print(const T &x)
{
int f = 0;
cerr << '{';
for (auto &i : x)
cerr << (f++ ? "," : ""), __print(i);
cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
__print(t);
if (sizeof...(v))
cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...) \
cerr << "[" << #x << "] = ["; \
_print(x)
#else
#define debug(x...)
#endif
class dsu
{
public:
vector<int> parent;
vector<int> size;
int n;
dsu(int n)
{
this->n = n;
parent.resize(n);
size.resize(n);
for (int i = 0; i < n; i++)
{
parent[i] = i;
size[i] = 1;
}
}
int find(int a)
{
if (parent[a] == a)
{
return a;
}
return parent[a] = find(parent[a]);
}
void unite(int a, int b)
{
a = find(a);
b = find(b);
if (a != b)
{
if (size[a] < size[b])
{
swap(a, b);
}
parent[b] = a;
size[a] += size[b];
}
}
};
void solve()
{
int n, m, q;
cin >> n >> m >> q;
vector<array<int, 2>> queries(q);
for (int i = 0; i < q; i++)
{
cin >> queries[i][0] >> queries[i][1];
}
vector<int> low(q, 1);
vector<int> high(q, m);
vector<int> ans(q, m);
while (true)
{
int flag = 0;
vector<int> mids[m + 1];
for (int i = 0; i < q; i++)
{
if (low[i] <= high[i])
{
int mid = (low[i] + high[i]) / 2;
mids[mid].push_back(i);
flag = 1;
}
}
if (flag == 0)
{
break;
}
dsu d(n + 1);
for (int i = 1; i <= m; i++)
{
int fac = m - i + 1;
for (int j = 2 * fac; j <= n; j += fac)
{
d.unite(j, fac);
}
for (auto it : mids[i])
{
int a = queries[it][0];
int b = queries[it][1];
if (d.find(a) == d.find(b))
{
ans[it] = i;
high[it] = i - 1;
}
else
{
low[it] = i + 1;
}
}
}
}
for (int i = 0; i < q; i++)
{
if (queries[i][0] == queries[i][1])
{
cout << 0 << endl;
}
else
{
cout << ans[i] << endl;
}
}
}
signed main()
{
fastio();
int t = 1;
while (t--)
solve();
return 0;
}
