#include <fstream>
#include <cmath>
using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");
long long prim(long long x)
{
    int i,nr=0;
    for(i=1;i<=x;i++)
        if(x%i==0)
        nr++;
    if(nr==2)
        return 1;
    else
        return 0;
}
int main()
{
    long long t,n,k,i,j,nr=0,aux,sw=0;
    fin>>t;
    for(aux=1;aux<=t;aux++)
    {  sw=0;
        fin>>n>>k;
        i=n;
        while(sw==0 && i!=0)
        {
            nr=0;
            for(j=1;j<=i;j++)
                if(i%j==0 && prim(j)==1)
                nr++;
                if(nr==0)
                    fout<<0<<'\n';
                else
                    if(nr==k)
                {
                    fout<<i<<'\n';
                    sw=1;
                }
            i--;
        }
    }
    return 0;
}