#include<stdio.h>
#include<math.h>
long *v=new long[1000001],a[1000001][8];
int main()
{long n,i,j,t,p,k,r;
v[1]=0; v[2]=0; v[3]=0;
j=1;
while(2*j<=1000000) {v[2*j]++;j++;}
for(i=3;i<=1000000;i+=2)
	{
	if (v[i]==0)
		{
		j=1;
		while(i*j<=1000000)
			{v[i*j]++;
			j++;}
		}

	}
for(i=1;i<=8;i++) a[1][i]=0;
for(i=2;i<=1000000;++i)
	{
	for(j=1;j<=8;j++) a[i][j]=a[i-1][j];
	a[i][v[i]]=i;
	}
FILE*f=fopen("divprim.in","r");
FILE*g=fopen("divprim.out","w");
fscanf(f,"%ld",&t);
for(i=1;i<=t;i++)
	{
	fscanf(f,"%ld %ld",&n,&k);
	fprintf(g,"%ld\n",a[n][k]);}
fclose(f);
fclose(g);
return 0;}