#include<fstream.h>
#include<stdlib.h>
int t,a[100][3];
void citire()
{ ifstream f("divprim.in");
  f>>t;
  int i,n,k;
  for(i=1;i<=t;i++)
      { f>>n>>k;
	a[i][1]=n;
	a[i][2]=k;
      }
  f.close();
}
int prim(int x)
{ int d;
  if(x==2) return 1;
  else { for(d=2;d<=x/2;d++)
	      if(x%d==0) return 0;
	 return 1;
       }
}
int div(int a)
{ int j,k=0;
  for(j=2;j<=a/2;j++)
      if(prim(j)==1 && a%j==0) k++;
  return k;
}
void prelucrare()
{ int i,j,ok=0;
  ofstream g("divprim.out");
  for(i=1;i<=t;i++)
     { ok=0;
       for(j=a[i][1]-1;j>=1;j--)
	   if(div(j)==a[i][2] && i!=t)
	     { g<<j<<"\n";
	       ok=1;
	       break;
	     }
	   if(div(j)==a[i][2] && i==t)
	     { g<<j<<"\n";
	       ok=1;
               break;
	     }

       if(ok==0 && i!=t) g<<"0\n";
       else if(i==t) g<<"0";
     }
  g.close();
}
int main()
{ citire();
  prelucrare();
  return 0;
}