#include <fstream>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int T,K,N;
int nrDivPrim(int n)
{
   int d=2,cnt=0;
   while(n!=1)
   {
       int p=0;
       while(n%d==0)
         {
             n/=d;
             p++;
         }
         if(p!=0) cnt++;
       if(d*d<n) d++;
        else d=n;
   }
    return cnt;
}
void Citire()
{
    fin>>T;
   while(T)
   {
       fin>>N>>K;
        while(N!=1)
        {
            if(nrDivPrim(N)==K)
            {
                fout<<N<<'\n';
                break;
            }
            N--;
        }
       if(N<2) fout<<0<<'\n';
        T--;
   }
}
int main()
{
    Citire();
    return 0;
}