#include<stdio.h>
#include<math.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
		{ if (a%2==0) r=1;
		else r=0;
		for (j=3; j<=a; j=j+2)
		  {	if (a%j==0)
				{ok=1;
				for (l=2; l<=sqrt(j);l++&&ok==1)
					if (j%l==0) ok=0;
				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;}