#include <bits/stdc++.h>
using namespace std;
#define imfaast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
struct node{
int L, R;
int l , r;
};
const int N=2e5 + 5;
int parent[N];
int find(int i){
if(parent[i] == -1)return i;
return parent[i] = find(parent[i]);
}
void merge(int x, int y){
x = find(x);
y = find(y);
if(x == y)return;
parent[y] = x;
}
void solve(){
int n, m, q;
cin>>n>>m>>q;
//for(auto it : v)cout << it.second <<' ';return;
vector<node>a;
for(int i = 0; i < q; i++){
int z, b;
cin>>z>>b;
node x;
x.L = z, x.R = b;
x.l = 0, x.r = m;
a.push_back(x);
}
bool lessa = 1;
while(lessa){
lessa = 0;
vi v[m + 1];
for(int i = 0; i < q; i++){
if(a[i].l + 1 != a[i].r){
lessa = 1;
v[a[i].l + a[i].r >> 1].push_back(i);
}
}
memset(parent, -1, sizeof parent);
for(int i = 1; i <= m; i++){
// i-th day
for(int j = (m - i + 1) * 2; j <= n; j += (m - i + 1))merge(m - i + 1, j);
for(auto j : v[i]){
if(find(a[j].R) == find(a[j].L)){
a[j].r = i;
}else {
a[j].l = i;
}
}
}
}
for(int i = 0; i < q; i++)cout<<a[i].r<<'\n';
}
int main(){
imfaast
int t=1;
// cin>>t;
while(t--){
solve();
}
}
