#include <iostream>
#include <fstream>

using namespace std;
int prim(int x)
{ int d,ok;
ok=1;
    if(x%2==0&&x>2||x<2)
        ok=0;
    else {for(d=3;d*d<=x;d+=2)
    {
       if(x%d==0)
            ok=0;
    }
    }
    return ok;

}

int main()
{
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    int N,K,d,T,i,nr,j;

    fin>>T;
    for(j=1;j<=T;j++)
       {
            cin>>N>>K;
        for(i=N;i>=1;i--)
        { nr=0;

            for(d=2;d*d<=i;d++)
            {
                if(i%d==0)

                    if(prim(d)==1)
                    nr++;
            }
            if(nr==K)
              {
                  fout<<i<<endl;
               break;
              }
        }
        if(i==0)
            fout<<0<<endl;

       }



    return 0;
}