#include<fstream>
using namespace std;
ifstream f1 ("divprim.in");
ofstream f2 ("divprim.out");
int v[1000001],m[1000001][8];
void ciur()
{
 int i,j;
 for (i=2; i<=1000000; i++)
   if (v[i]==0)
      for (j=i; j<=1000000; j+=i) v[j]++;
}
rezolvare()
{
int i,j;
for (i=1; i<=7; i++) m[1][i]=0;
for (i=2; i<=1000001; i++)
 {
   for (j=1; j<=7; j++) m[i][j]=m[i-1][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;
}