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