#include <bits/stdc++.h>
using namespace std ;
const int N = 2e5+5 ;
const int L = 23 ;
int n , m , q ;
struct Reachability_Tree {
vector <int> g[N] ;
int par[N] , w[N] , rt ;
void init () {
rt = n ;
for ( int i = 1 ; i < 2*n ; i++ ) {
par[i] = i ;
}
}
int fin ( int x ) {
if ( x == par[x] ) {
return x ;
}
return par[x] = fin ( par[x] ) ;
}
bool uni ( int x , int y , int we ) {
if ( ( x = fin(x) ) == ( y = fin(y) ) ) {
return 0 ;
}
rt++ ;
par[x] = rt ;
par[y] = rt ;
g[rt].push_back(x) ;
g[rt].push_back(y) ;
w[rt] = we ;
return 1 ;
}
} krt ;
struct LCA_Sparse_Table {
int in[N] , eu[N<<1] , logs[N<<1] , st[N<<1][L] , t = 0 ;
void tour ( int i ) {
t++ ;
eu[t] = i ;
in[i] = t ;
for ( auto it : krt.g[i] ) {
tour ( it ) ;
t++ ;
eu[t] = i ;
}
}
void build () {
logs[1] = 0 ;
for ( int i = 2 ; i <= t ; i++ ) {
logs[i] = logs[i>>1] + 1 ;
}
for ( int i = 1 ; i <= t ; i++ ) {
st[i][0] = eu[i] ;
}
for ( int j = 1 ; j <= logs[t] ; j++ ) {
for ( int i = 1 ; i + ( 1 << j ) - 1 <= t ; i++ ) {
int x = st[i][j-1] , y = st[i+(1<<(j-1))][j-1] ;
st[i][j] = ( in[x] < in[y] ? x : y ) ;
}
}
}
int query ( int x , int y ) {
x = in[x] ;
y = in[y] ;
if ( x > y ) {
swap ( x , y ) ;
}
int j = logs[y-x+1] ;
x = st[x][j] ;
y = st[y-(1<<j)+1][j] ;
return ( in[x] < in[y] ? x : y ) ;
}
} lca ;
inline void solve () {
cin >> n >> m >> q ;
krt.init () ;
for ( int i = 1 ; i <= m ; i++ ) {
int g = m-i+1 ;
for ( int j = 2*g ; j <= n ; j += g ) {
krt.uni ( g , j , i ) ;
}
}
lca.tour ( krt.rt ) ;
lca.build () ;
while ( q-- ) {
int x , y ;
cin >> x >> y ;
cout << krt.w[lca.query(x,y)] << "\n" ;
}
}
signed main () {
//freopen ( ".in" , "r" , stdin ) ;
//freopen ( ".out" , "w" , stdout ) ;
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cout.tie(0) ;
int tc = 1 ;
//cin >> tc ;
while ( tc-- ) {
solve() ;
}
return 0 ;
}
/// JJJJJJJ EEEEEEE AAAAA NN NN 7777777
/// JJ EE AA AA NNN NN 77
/// JJ EEEEEE AAAAAAA NN N NN 77
/// JJ JJ EE AA AA NN NNN 77
/// JJJJJ EEEEEEE AA AA NN NN 77
