#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int main()
{
   int T,N,K;
  f>>T;
   for(int i=0;i<T;i++)
   {
   f>>N>>K;

       int X=N-1,ok=1;
       while(ok==1 && X>0)
       {int nr=0,d=2,aux=X;
           while(aux>1)
           {
             if(aux%d==0)
             {
                 nr++;
                 while(aux%d==0)
                    aux=aux/d;
             }
             d++;
           }
           if(nr==K)

           {     g<<X<<endl;
               ok=0;
           }
           else
            X--;
       }
       if(ok==1)
         g<<0<<endl;

   }
    return 0;
}