#include <fstream>
using namespace std;
ifstream fi("divprim.in");
ofstream fo("divprim.out");
const int Dim=1000000;

int t,n,k,a[Dim+1][8],i,j,prim[Dim+1];

int main()
{

for(i=2;i<=Dim;i++)
if (prim[i]==0) for (j=i;j<=Dim;j+=i) prim[j]++;

for(i=2;i<=Dim;i++)
for(j=0;j<=7;j++)
if (prim[i]==j) a[i][j]=i;
           else a[i][j]=a[i-1][j];

fi>>t;

 for(i=1;i<=t;i++)
 {fi>>n>>k;
  fo<<a[n][k]<<'\n';}

return 0;
}