#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 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,2)==1)
					nrdivprim++;

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

			}
		}

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

       }
return 0;
}