#include<stdio.h>
int main()
{long  n,i,j,k,t,ok,a,l,r,okp=1;;
FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");
fscanf(f,"%ld",&t);
for (i=1; i<=t; i++)
	{
	fscanf(f,"%ld %ld",&n,&k);
	a=n;  okp=1;
	do
		{  r=0;
		for (j=2; j<=a; j++)
		  {	if (a%j==0)
				{ok=1;
				for (l=2; l<=j/2;l++)
					if (j%l==0) {ok=0; break;}
				if (ok==1) r++;} }
		  if (r==k){fprintf(g,"%ld\n",a);  okp=0;  }
		  a--;}
	while (okp==1&&a>=2);
	if (a==1) fprintf(g,"0\n");
}
fclose(f);
fclose(g);
return 0;}