#include<cstdio>
#include<cmath>
int ciur[1000001],i,j,n,m,a[8][1000001],k,x;
int main ()
{
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);
int p=2,up=sqrt(1000000);
while(p<=up)
	{
	for(i=1;i*p<=1000000;i++)
		ciur[i*p]++;
	p++;
	while(ciur[p]!=0)
		p++;
	}
for(i=1;i<=1000000;i++)
	{
	x=ciur[i];
	for(j=1;j<=7;j++)
		{
		if(j==ciur[i])
			a[j][i]=i;
		else
			a[j][i]=a[j][i-1];
		}
	}
int t;
scanf("%d",&t);
for(i=1;i<=t;i++)
	{
	scanf("%d%d",&n,&k);
	if(k==0)
		printf("1\n");
	else
		printf("%d\n",a[k][n]);
	}
return 0;
}