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

int main()
{	ifstream f("divprim.in");
	ofstream g("divprim.out");
	int k,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--)
		{       prim=0;
			if(j%2==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) prim++;
						else prim=0;
					}
			}
			else
			{	for(div=3;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) prim++;
						else prim=0;
					}
			}
			if(k==prim) {g<<j<<'\n';sw=1;}
		}
		if(!sw) g<<0<<'\n';
	}
	f.close();
	g.close();
	return 0;
}