#include<fstream.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;
		for (j=2; j<=a/2; j++)
		  {	if (a%j==0)
				{ok=1;
				for (l=2; l<=j/2;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";}
f.close();
g.close();
return 0;}