#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
long long aux[1000005],i,j,n,x,k,ok;
int main()
{
    aux[1]=0;
    aux[2]=0;
    for(i=2;i<=50000;i++)
    {
        if(aux[i]==0)
        {
            aux[i]=1;
            for(j=2*i;j<=1000000;j=j+i)
            {
                aux[j]++;
            }
        }
    }
    /*for(i=1;i<=100;i++)
    {
        cout<<i<<" "<<aux[i]<<endl;
    }*/
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x>>k;
        ok=0;
        for(j=x;j>=1;j--)
        {
            if(aux[j]==k)
            {
                cout<<j<<endl;
                ok=1;
                break;
            }
        }
        if(ok==0)
        {
           cout<<0<<endl;
        }
    }
    return 0;
}