#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;
 memset(div,0,sizeof(div));
 for(i=2;i<=n;i++)
	if(!div[i]) for(j=i;j<=n;j+=i)
			div[j]++;
}

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