#include<fstream>
using namespace std;
ifstream f1 ("divprim.in");
ofstream f2 ("divprim.out");
int divizori (int k)
  {int c=0,s,i;
   for (i=2; i*i<=k; i++)
      {s=0;
       while (k%i==0) {k/=i; s++;}
       if (s>0) c++;}
   if (k>1) c++;
   return c;}
int main()
  {int n,k,t,i;
   f1>>t;
   for (i=1; i<=t; i++)
     {f1>>n>>k;
     while (divizori(n)!=k && n>0) n--;
     f2<<n<<endl;}
  f1.close();
  f2.close();
  return 0;
  }