#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int N,T,X,K,i,ok,m,d;
int prim(int n)
{
    int d,ok=1;
    for(d=2;d*d<=n;d++)
        if(n%d==0)
    {
        ok=0;
        break;
    }
    return ok;
}
int main()
{
    f>>T;
    for(i=1;i<=T;i++)
    {
        f>>N>>K;
        if(N==1)
            g<<0<<endl;
        else
        {
           for(X=N;X>=2;X--)
           {
               m=0;
               for(d=2;d*d<=X;d++)
                   if(X%d==0)
                   {
                        if(prim(d)==1)
                            m++;
                        if(X/d!=d)
                            if(prim(X/d)==1)
                                m++;
                   }
              if(m==K)
              {
                    g<<X<<endl;
                    break;
              }
           }
           if(X==1)
            g<<0<<endl;
        }
    }
}