#include<stdio.h>
const long maxn=1000007;
long n,k,b[maxn][8],a[maxn],i,t,j;
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	b[1][0]=0;
	for(i=2;i<maxn;i++)
	{
		if(!a[i])
			for(j=i;j<maxn;j+=i)//ciur
				++a[j];
		for(j=0;j<=7;j++)//k<=7 
			b[i][j]=b[i-1][j];
		if(a[i]<=7)//daca a[i]<=7 noua pozitie
			b[i][a[i]]=i;
	}
	scanf("%ld",&t);//nr teste
	for(i=1;i<=t;i++)
	{
		scanf("%ld %ld",&n,&k);//n,k
		printf("%ld\n",b[n][k]);
	}
	return 0;
}