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

}


long int t,i,j,div,x,y,nrdivprim,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--)
		{

		nrdivprim=0;
		for(div=2;div<=j/2;div++)
			if(j%div==0)
				if(prim(div)==1)
					nrdivprim++;

		if(nrdivprim==y)
			{
			printf("%li\n",j);
			ok=1;
			break;

			}
		}

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

       }
return 0;
}