#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*i<=x;i++) {
        if(x%i==0 && i*i!=x)
            nr+=2;
        else if(i*i==x)
            nr+=1;
    }
    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 * j <=i;j++) {
                if(i%j==0 && prim(j)==1)
                    nr++;
                if (i % (i / j) == 0 && prim(i / j) && j != i / j)
                    nr++;
            }
            if(nr==0)
                fout << 0 << '\n';
            else if(nr==k) {
                fout<<i<<'\n';
                sw=1;
            }
            i--;
        }
    }
    return 0;
}