#include<fstream.h>
int n,t,kdiv[1000001],k,i,j,sol[1000001][9];
int main()
{ifstream q("divprim.in");
ofstream w("divprim.out");
for(i=2;i<=1000001;i++)
   if(!kdiv[i])
    for(j=i;j<=1000001;j+=i)
kdiv[j]++;
for(i=2;i<1000001;i++)
  {for(j=0;j<=7;j++)
     sol[i][j]=sol[i-1][j];
  sol[i][kdiv[i]]=i;}
q>>t;
for(j=1;j<=t;j++)
  {q>>n>>k;
  w<<sol[n][k];}
return 0;}