#include<stdio.h>
long int i,j,ciur[1000001],sol[1000001][9],t,n,k;
int main()
{
	FILE *f,*g;
	f=fopen("divprim.in","r");
	g=fopen("divprim.out","w");
	for(i=2;i<=1000000;i++)
	 if(!ciur[i])
	  for(j=i;j<=1000000;j=j+i)
	   ciur[j]++;
	for(i=1;i<=1000000;i++)
	 {for(j=1;j<=8;j++)
	   sol[i][j]=sol[i-1][j];
	  sol[i][ciur[i]]=i;
	 }
	fscanf(f,"%ld",&t);
	for(i=1;i<=t;i++)
	{ fscanf(f,"%ld%ld",&n,&k);
	  fprintf(g,"%ld\n",sol[n][k]);
	}
	fcloseall();
	return 0;
}