#include<stdio.h>
#include<math.h>

long m,k,n,p,i,j,ma[8][1000001],div[1000001],nr;

int main()
{
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);
scanf("%ld",&m);
//for(i=;i<=1000000;i++)
	//b[i]=0;
for(i=2;i<=1000000;i++)
{
	if(div[i]== 0 )
	{
		p = 1000000/i;
		for(j=1;j<=p;j++)
			div[i*j]++;
		
	}
	
}
for(k=1;k<=7;k++)
{
	nr=0;
	for(j=0;j<=1000000;j++)
	{
	if(k==div[j])
        nr=j;
	ma[k][j]=nr;
	}
}
for(i=1;i<=m;i++)
{
	scanf("%ld%ld",&n,&k);
	printf("%ld\n",ma[k][n]);
}	
return 0;
}