#include<fstream.h>
ifstream f("divprim.in");
ofstream g("divprim.out");
int t,k,n,ok,gasit,v[8];
int main()
{
	f>>t;
	v[1]=2,v[2]=3,v[3]=5,v[4]=7,v[5]=11,v[6]=13,v[7]=17;
	for(int i=1;i<=t;i++)
	{
		f>>n>>k;
		gasit=0;
		if(k==0)
			g<<n;
		else
			while(n>v[k] && !gasit)
			{
				ok=1;
				for(int j=1;j<=k;j++)
					if(n%v[j]!=0)
						ok=0;
				if(ok==1)
				{
					g<<n<<'\n';
					gasit=1;
				}
				else
					n--;
			}
		if(n<=v[k])
			g<<'0'<<'\n';
	}
	f.close();
	g.close();
	return 0;
}