#include<fstream.h>

  ifstream f("divprim.in");
  ofstream g("divprim.out");
  int x[7]={2,3,5,7,11,13,17},b,c,k,o;
  long p,n,i,a,j;
int main()
{
 f>>n;
 for(i=1;i<=n;i++)
 {
  f>>a;
  f>>b;
 o=0;
	p=1;
	for(k=0;k<=b-1;k++)
	  p=p*x[k];
	for(j=a;j>=1;j--)
	{
	  if(j%p==0)
		{
			g<<j<<"\n";
			o=1;
			break;
		}
	 }
		  if(o==0)
	  g<<0<<"\n";
}
 f.close();
 g.close();
 return 0;
}