#include<stdio.h>
#define LMAX 1000005

long div[LMAX+1],k;  long t,n,i,j,sol[LMAX+1][9];

void generare()
{for(i=2;i<=LMAX;i++)
 if(div[i]==0)
 for(j=i;j<=LMAX;j+=i) div[j]++;

 sol[1][0]=1;

 for(i=2;i<=LMAX;++i)
 {
 for(j=0;j<=7;j++) sol[i][j]=sol[i-1][j];
 sol[i][div[i]]=i;}


}

main()
{freopen("divprim.in","r",stdin);
 freopen("divprim.out","w",stdout);

 generare();

 scanf("%ld",&t);
 for(i=1;i<=t;i++)
 {scanf("%ld %d",&n,&k);
  printf("%ld\n",sol[n][k]);}
}