#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
const int lim=2e5+100;
#else
const int lim=1e4+100;
#endif
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define pb push_back
const int mod=1e9+7;
using pii=pair<int,int>;
int parent[lim],sz[lim],t[lim];
int find(int i){
if(parent[i]==i)return i;
return find(parent[i]);
}
void unite(int i,int j,int tm){
int x=find(i),y=find(j);
if(x==y)return;
if(sz[x]<sz[y])swap(x,y);
t[y]=tm;
parent[y]=x;
sz[x]+=sz[y];
}
int find(int i,int tm){
if(parent[i]==i||tm<t[i])return i;
return find(parent[i],tm);
}
inline void solve(){
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
parent[i]=i;
}
for(int i=1;i<=m;i++){
int inc=m-i+1;
for(int j=inc;j<=n;j+=inc){
unite(inc,j,i);
}
}
while(q--){
int a,b;
cin>>a>>b;
int l=1,r=m-1,ans=m;
while(l<=r){
int mid=(l+r)>>1;
int x=find(a,mid),y=find(b,mid);
if(x==y){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#else
//freopen("boards.in","r",stdin);
//freopen("boards.out","w",stdout);
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
