#include<stdio.h>
long int prim(long int x,long int i)
{
if(i>x/2)
	return 1;
if(x%i==0)
	return 0;
return prim(x,i+1);

}
long int nrdivprimi(long int j,long int i,long int s)
{
if(i>j/2)
	return s;
if(j%i==0 && prim(i,2)==1)
	s++;
return nrdivprimi(j,i+1,s);

}

long int t,i,j,div,x,y,ok;
int main()
{
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);
scanf("%li",&t);

for(i=0;i<t;i++)
       {
	scanf("%li %li",&x,&y);
	ok=0;
	for(j=x;j>1;j--)
		{
		if(nrdivprimi(j,2,0)==y)
			{
			printf("%li\n",j);
			ok=1;
			break;
			}
		}

	 if(ok==0)
		printf("0\n");

       }
return 0;
}