#include<cstdio>
long long N,copie,prim[12],t=0,P;
void divprim()
{
    long long i;
    copie=N;
    for(i=2;i*i<=N;++i)
        if(copie%i==0)
        {
            prim[++t]=i;
            while(copie%i==0)
                copie/=i;
        }
    if(copie!=1)
        prim[++t]=copie;
}

void calcul( long long x, long long &nrb,long long &prod)
{
    nrb=0;
    prod=1;
    int i=1;
    while(x)
    {
        if(x&1)
        {
            nrb++;
            prod*=prim[i];
        }
        i++;
        x>>=1;
    }
}

long long f(long long x)
{
    long long i,prod,nrb,s=0;
    for(i=0;i<(long long)1<<t;++i)
    {
        calcul(i,nrb,prod);
        if(nrb&1)
            s-=x/prod;
        else
            s+=x/prod;
    }
    return s;
}

long long rez()
{
    long long st=1,dr=(long long)1<<(long long)61,m;
    while(st!=dr)
    {
        m=(st+dr)/2;
        if(f(m)>=P)
            dr=m;
        else
            st=m+1;
    }
    return st;
}

int main()
{
    FILE*f=fopen("frac.in","r");
    FILE*h=fopen("frac.out","w");
    fscanf(f,"%lld%lld",&N,&P);
    divprim();
    fprintf(h,"%lld\n",rez());
    return 0;
}int main()
{
    int t,n,k;
    ciur();
    fscanf(f,"%d",&t);
    for ( int i=1;i<=t;++i ){
        fscanf(f,"%d%d",&n,&k);
        int p=0;
        for ( int pas=1<<24;pas;pas/=2 )
            if ( p+pas<=v[k][0]&&v[k][p+pas]<=n )
                p+=pas;
        if ( v[k][1]>n )
            fprintf(h,"0\n");
        else
            fprintf(h,"%d\n",v[k][p]);
    }
    return 0;
}