#include<fstream>
#include<cstdio>
using namespace std;
int T,nrdprim[1000100],sol[8][1000100];

int main()
{
	int i,j,n,K;
	for(j=2;j<=1000000;j+=2)
		nrdprim[j]=1;
	for(i=3;i<=1000000;i+=2)
	{
		if(nrdprim[i]==0)
		{
			for(j=i;j<=1000000;j+=i)
				nrdprim[j]++;
		}
	}
	for(i=1;i<=1000000;i++)
	{
		for(j=0;j<=7;j++)
			sol[j][i]=sol[j][i-1];
		sol[nrdprim[i]][i]=i;
	}
	
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&K);
		printf("%d\n",sol[K][n]);
	}
	return 0;
}