# include <stdio.h>
# define nmax 1000001
int c[nmax],a[8][nmax];
void ciur(long n)
{
	c[1]=0;
	c[0]=-1;
	long i,j;
	for (i=4; i<=n; i=i+2) c[i]=1;
	c[2]=1;
	for (i=3; i<=n; i=i+2)
		if (!c[i])
		{
			for (j=i+i; j<=n; j=j+i)
				c[j]++;
			c[i]=1;
		}
}
long n,m,t,k;
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	ciur(nmax);
	int i,j;
	for (i=0;i<=7;i++)
		for (j=1;j<=nmax; j++)
			if (c[j]==i) a[i][j]=j;
				else a[i][j]=a[i][j-1];
	for (k=1;k<=t;k++)
	{
		scanf("%d%d",&n,&m);
		printf("%d\n",a[m][n]);
	}
}