#include<fstream.h>
#include<math.h>
int main()
{long int n,i,j,k,t,ok,a,l,r,okp=1;;
ifstream f("divprim.in");
ofstream g("divprim.out");
f>>t;
for (i=1; i<=t; i++)
	{
	f>>n; f>>k;
	a=n;  okp=1;
	do
		{  r=0;ok=1;
		for (j=2; j<=sqrt(a); j++&&ok==1)
			if (a%j==0)ok=0;
		if (ok==1) {if (k==1) g<<a<<"\n";   }
		else
			{for (j=2; j<=a/2; j++)
		  {	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){g<<a<<"\n";  okp=0;  }}
		  a--;}
	while (okp==1&&a>=2);
	if (a==1) g<<"0\n";
}return 0;}