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

#define max 1000002

 char x[max];
 long m[max][8];
 long i,a,b,n,j,ok;
 ifstream f("divprim.in");
 ofstream g("divprim.out");
void prime()
{
 long c=2,i;
 while(c<=sqrt(1000000))
 {
  for(i=2*c;i<=1000000;i+=c)
	x[i]++;
  do{ c++;
  }
  while (x[c]);
 }
}

int main()
{
 prime();
 f>>n;
 for(i=1;i<=n;i++)
 {
  f>>a;
  f>>b;
  ok=0;
   for(j=a;j>=1;j--)
    if(x[j]==b)
    {
     g<<j<<"\n";
   ok=1;
     break;
   } 
   if(ok==0)
    g<<0<<"\n";
  }             
 f.close();
 g.close();
 return 0;
}