#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define NTABLES 3
#define TSIZE   50000
#define PLIST   50000


typedef struct bin{
  int len;
  int *digits;} binary;


int primes[PLIST];

int primetest(int n){
  int i, primecheck=1;

  for(i=2; i<sqrt((float)n); i++)
    if(n%i==0) {primecheck=0; break;}

  return primecheck;
}


binary dec_to_bin(int n){
  int i, j, k, m;
  binary bin;
  for(i=0, j=1; j<=n; i++)
    j=j*2;

  if(i==0) i=1;

  bin.len=i;
  bin.digits=(int *)malloc(i*sizeof(int));
  
  m=n;

  for(j=0; j<i; j++){
    k=m%2;
    bin.digits[j]=k;
    m=m/2;
  }

  return bin;
}


int power(int base, int exponent, int modulo){
  binary bin, prod;
  int i, j;

  bin=dec_to_bin(exponent);
  prod.digits=(int *)malloc(i*sizeof(int));
  prod.digits[0]=base%modulo;
  for(i=1;i<bin.len; i++){
    prod.digits[i]=(prod.digits[i-1]*prod.digits[i-1])%modulo;
  }
  j=1;
  for(i=0; i<bin.len; i++){
    if(bin.digits[i]==1){
      j*=prod.digits[i];
      j=j%modulo;
    }
  }
  return j;
}

//this computes the value of (q/p)

int legendre(int q, int p){
  int res;
  if(q%p==2){
    if(p%8==1 || p%8==7) return 1;
    else return -1;
  }

  if(q>p) res=power(q, (p-1)/2, p);
  if(p>q) {
    res=power(p, (q-1)/2, q);
    if(p%4==3 && q%4==3) res=q-res;
  }
  if(res==1) return 1;
  else return -1;
}


//lowest quad nonresidue mod p
int Np(int p){
  int i;
  for(i=0; i<PLIST; i++){
    if(legendre(primes[i], p)!=1)
      return primes[i];
  }
}

//lowest non-q'th power residue mod p
int Npq(int p, int q){
  int i;
  for(i=0; i<PLIST; i++){
    if(power(primes[i], (p-1)/q, p)!=1)
      return primes[i];
  }
}
    
    

main(){
  binary b;
  int i, n,j,currentprime, primecheck, max;
  int mat[NTABLES][TSIZE], size[NTABLES], currenttable,k, t;

  /*********************************************************/
  /********** init prime array up to the 50000th prime******/
  /****************ie  611951  *****************************/

  primes[0]=2;
  primes[1]=3;
  primes[2]=5;
  primes[3]=7;
  primes[4]=11;
  primes[5]=13;
  primes[6]=17;
  primes[7]=19;
  primes[8]=23;
  primes[9]=29;

 
  currentprime=10;

   for(i=5; currentprime<PLIST-1;i++){
    n=6*i+1;primecheck=1;
    for(j=2; j<currentprime && primes[j]*primes[j]<=n; j++){
      if((n%primes[j])==0){
	primecheck=0;
	break;}
    }

    if(primecheck==1) primes[currentprime++]=n;

    n=6*i+5;primecheck=1;
    for(j=2; j<currentprime && primes[j]*primes[j]<=n; j++){
      if((n%primes[j])==0){
	primecheck=0;
	break;}
    }

    if(primecheck==1) primes[currentprime++]=n;
  }
   /************** done init prime array*************/

   // printf("last prime %d %d\n", primes[currentprime-1], currentprime);

   //  printf("%d\n",Npq(7, 3));

   max=1;

   scanf("%d", &n);
   for(i=0; i<999998; i++){
     scanf("%d", &n);
     // printf("%d  \n", Np(n));
     j=Np(n);
     if(j>max) max=j;
     }

   printf("%d\n", max);

   

   
}