#include<stdio.h>
#define maxn 1000005
long i,j,t,a[maxn],k,p,sol[maxn][10];
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	for(i=2;i<maxn;i++)
		if(a[i]==0)
			for(j=i;j<=maxn;j+=i)
				a[j]++;
	for(i=2;i<=maxn;i++)
		if(a[i]<=7)
	sol[i][a[i]]=i;
	for(i=2;i<=maxn;i++)
		for(j=1;j<=8;j++)
			if(sol[i][j]==0)
				sol[i][j]=sol[i-1][j];
	scanf("%ld",&t);
	for(i=1;i<=t;i++){
		scanf("%ld %ld",&p,&k);
		printf("%ld\n",sol[p][k]);}
	return 0;
}