#include<stdio.h>
#include<string.h>
FILE*f=fopen("divprim.in","r");
FILE*g=fopen("divprim.out","w");
long t,n;
int k,div[1000000],mat[1000000][8];

void ciur()
{
 long i,j;
 for(i=2;i<=1000000;i++)
	if(!div[i]) for(j=i;j<=1000000;j+=i)
			div[j]++;
}

int main()
{
 long i,j,p;
 ciur();
 for(j=1;j<=1000000;j++)
	{
	 for(p=1;p<=7;p++)
		mat[j][p]=mat[j-1][p];
	 mat[j][div[j]]=j;
	}
 fscanf(f,"%ld",&t);
 for(i=1;i<=t;i++)
	{
	 fscanf(f,"%ld%d",&n,&k);
	 fprintf(g,"%d\n",mat[n][k]);
	}
 fcloseall();
 return 0;
}