# include <stdio.h>
# define nmax 1000001
int c[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);
	for (k=1;k<=t;k++)
	{
		scanf("%d%d",&n,&m);
		while (n>0 && c[n]!=m) n--;
		printf("%d\n",n);
	}
}