#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;
  if(b==0)
	g<<1;
  if(b==1 && a>=9)
	g<<9<<"\n";
  if(b==1 && a<9)
	 g<<0<<"\n";
  if(b!=1)
  {
	p=1;
	for(j=a;j>=1;j--)
	{
     c=0;
      for(k=0;k<=b-1;k++)
        if(j%x[k]==0)
         c++;
      if(c==b)
       {
         g<<j<<"\n";
         o=1;
         break;
         }       
    }
        if(o==0)
     g<<0<<"\n";
}
 }
 f.close();
 g.close();
 return 0;
}