#include<fstream>
using namespace std;
ifstream f1 ("divprim.in");
ofstream f2 ("divprim.out");
int v[1000001],m[1000001][8],i,j;
void ciur()
{
 for (i=2; i<=1000000; i++)
   if (v[i]==0)
      for (j=i; j<=1000000; j+=i) v[j]++;
}
void rezolvare()
{
for (i=2; i<=1000000; i++)
 {
   j=1;
   while (m[i-1][j]>0) {m[i][j]=m[i-1][j]; j++;}
   m[i][v[i]]=i;
 }
}
int main()
  {int n,k,t,i;
   f1>>t;
   ciur();
   rezolvare();
   for (i=1; i<=t; i++)
     {f1>>n>>k;
      f2<<m[n][k]<<endl;
     }
   return 0;
}