#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
int c[1000005];
int i,j,n,x,k,d,nr,ok;
int main()
{
    c[0]=c[1]=1;
    c[2]=0;
    for(i=2; i<=1000; i++)
    {
        if(c[i]==0)
        {
            for(j=2; i*j<=1000000; j++)
            {
                c[i*j]=1;
            }
        }
    }
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>x>>k;
        ok=0;
        while(ok==0)
        {
            nr=0;
            for(d=2; d<=x/2; d++)
            {
                if(x%d==0&&c[d]==0)
                {
                    nr++;
                }
            }
            //cout<<x<<' '<<nr<<' ';
            if(nr==k)
            {
                cout<<x<<'\n';
                ok=1;
            }
            if(x==1)
            {
                break;
            }
            x--;
        }
        if(ok==0)
        {
            cout<<0<<'\n';
        }

    }
    return 0;
}