#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define pb push_back

int id[100100];
int sz[100100];

int find(int x){
    if(x == id[x]) return x;
    return id[x] = find(id[x]);
}

void uni(int p, int q){
    p = find(p);
    q = find(q);
    if(p==q) return;
    if(sz[p]>sz[q]) swap(p, q);
    id[p] = q;
    sz[q] += sz[p];
    return;
}

int main(){ _
    int n, m, q;
    int ans[100100], a[100100], b[100100];

    cin >> n >> m >> q;

    for(int i=0; i<=n; i++){id[i] = i, sz[i]=1;}

    for(int i=0; i<q; i++){
        cin >> a[i] >> b[i];
        ans[i] = m;
    }

    for(int i=m; i>0; i--){
        for(int j=i+i; j<=n; j+=i){
            uni(i, j);
        }
        for(int j=0; j<q; j++){
            if(ans[j] == m and find(a[j]) == find(b[j])){
            //  cout << find(a[j]) << " " << find(b[j]) << endl;
                ans[j] = m-i+1;
            }
        }
    }

    for(int i=0; i<q; i++)
        cout << ans[i] << endl;


    exit(0);
}