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

 int x[1000001];
 long m[1000001][8];
 long i,a,b,n;
 ifstream f("divprim.in");
 ofstream g("divprim.out");
void prime()
{
 long c=2,i;
 while(c<=1000)
 {
  for(i=2*c;i<=1000000;i+=c)
	x[i]++;
  do{ c++;
  }while (x[c]);
 }
}
void matrice()
{long k;
 for(long i=1;i<=1000000;i++)
	for(int j=1;j<=7;j++)
    {
      if(m[i][j-1]==0 && j>=2)
      {
         for(k=j;k<=7;k++)
          m[i][k]=0;
      }
      else
      {
      
      for(k=i;k>=1;k--)
       if(x[k]==j)
	   {
		m[i][j]=k;
		break;
	  }
    }}
}
int main()
{
 prime();
 matrice();
 f>>n;
if(n%2==0)
 for(i=1;i<=n;i+=2)
 {
  f>>a;
  f>>b;
 	g<<m[a][b]<<"\n";
  f>>a;
  f>>b;
   g<<m[a][b]<<"\n"; 	
 	
}         
else
{
 f>>a;f>>b;
 g<<m[a][b]<<"\n";
 for(i=1;i<=n;i+=2)
 {
  f>>a;
  f>>b;
 	g<<m[a][b]<<"\n";
  f>>a;
  f>>b;
   g<<m[a][b]<<"\n"; 	
}        
}             
 f.close();
 g.close();
 return 0;
}