rt

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node
{
    int u,v,nxt,w;
}e[maxn<<1];
int head[maxn],tot;
void add(int u,int v,int w)
{
    e[++tot].u=u;
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int fa[maxn],n,m,q,f[maxn][25],ma[maxn][25];
int getfa(int x)
{
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
int de[maxn];
void dfs(int x,int fa)
{
    // cout<<x<<endl;
    de[x]=de[fa]+1;
    f[x][0]=fa;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v!=fa)
        {
            dfs(v,x);
            ma[v][0]=e[i].w;
        }
    }
}
int lca(int x,int y)
{
    if(de[x]<de[y])
        swap(x,y);
    int s=0;
    for(int i=20;i>=0;i--)
    {
        if(de[f[x][i]]>=de[y])
        {
            s=max(s,ma[x][i]);
            x=f[x][i];
        }
    }
    if(x==y)
        return s;
    for(int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
            s=max(s,max(ma[x][i],ma[y][i]));
        }
        else   
            break;
    }
    return max(s,max(ma[x][0],ma[y][0]));
}

int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)   
        fa[i]=i;
    for(int i=m;i>=1;i--)
    {
        for(int j=i<<1;j<=n;j+=i)
        {
            if(getfa(i)!=getfa(j))
            {
                add(i,j,m-i+1);
                // cout<<i<<' '<<j<<' '<<m-i+1<<endl;
                add(j,i,m-i+1);
                fa[getfa(i)]=getfa(j);
            }
        }
    }   
    dfs(1,1);
    // cout<<"OK";
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
        {
            f[j][i]=f[f[j][i-1]][i-1];      
            ma[j][i]=max(ma[j][i-1],ma[f[j][i-1]][i-1]);
        }
    for(int i=1;i<=q;i++)
    {
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
    return 0;
}