#include <stdio.h>
#define max 1000000
#define D 1000001

int T,N,K,i,j;
int p[D],Mat[D][8];

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

	for(i=2;i<=max;i++)
		if(p[i]==0)
			for(j=i;j<=max;j+=i)
				p[j]++;
	for(i=2;i<=max;i++)
	{
		for(j=0;j<8;j++)
			Mat[i][j]=Mat[i-1][j];
		Mat[i][p[i]]=i;
	}

	scanf("%d",&T);
	for(i=1;i<=T;i++)
	{
		scanf("%d%d",&N,&K);
		printf("%d\n",Mat[N][K]);
	}

	return 0;
}