#include<fstream.h>
#include<math.h>

int main()
{	ifstream f("divprim.in");
	ofstream g("divprim.out");
	int k,k_div_prim,ok,sw;
	unsigned long t,n,div,i,j,d;
	f>>t;
	for(i=1;i<=t;i++)
	{	f>>n>>k;sw=0;
		for(j=n;j>=2&&!sw;j--)
		{       k_div_prim=0;
			for(div=2;div<=j/2;div++)
				if(j%div==0)
				{	d=2;ok=1;
					while(d<=sqrt(div)&&ok)
						if(div%d==0) ok=0;
						else d++;
					if(ok) k_div_prim++;
					else k_div_prim=0;
				}
			if(k==k_div_prim) {g<<j<<'\n';sw=1;}
		}
		if(!sw) g<<0<<'\n';
	}
	f.close();
	g.close();
	return 0;
}