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


long primes[PLIST], binrep[100];

long int offset[10]={350000001, 400000001, 450000001, 500000001, 550000001, 600000001, 650000001, 700000001, 750000001, 800000001};

char *filenames[10]={"primes350mil_up.fil","primes400mil_up.fil","primes450mil_up.fil","primes500mil_up.fil","primes550mil_up.fil","primes600mil_up.fil","primes650mil_up.fil","primes700mil_up.fil","primes750mil_up.fil","primes800mil_up.fil"};


char *outputs[10]={"np350mil_up.fil","np400mil_up.fil","np450mil_up.fil","np500mil_up.fil","np550mil_up.fil","np600mil_up.fil","np650mil_up.fil","np700mil_up.fil","np750mil_up.fil","np800mil_up.fil"};



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

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

  return primecheck;
}


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

  if(i==0) i=1;

  len=i;
  
  m=n;

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

  return len;
}


long power(int base, int exponent, int modulo){
  long prod[100];
  long i, j, len;

  len=dec_to_bin(exponent);
  prod[0]=base%modulo;
  for(i=1;i<len; i++){
    prod[i]=(prod[i-1]*prod[i-1])%modulo;
  }
  j=1;
  for(i=0; i<len; i++){
    if(binrep[i]==1){
      j*=prod[i];
      j=j%modulo;
    }
  }
  return j;
}

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

long legendre(long q, long p){
  long 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
long Np(long p){
  long i;
  for(i=0; i<PLIST; i++){
    if(legendre(primes[i], p)!=1)
      return primes[i];
  }
}

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

main(){
  long i, n,j,currentprime, primecheck, max, maxn;
  long mat[NTABLES][TSIZE], size[NTABLES], currenttable,k, t;
  FILE * in, *out;
  int start;

  /*********************************************************/
  /********** 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));

   /*   for(start=0; start<10; start++){
     in=fopen(filenames[start], "r");
     out=fopen(outputs[start], "w");*/
   

   max=1;

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

   printf("\n\n\n");
  // fclose(out);
  // fclose(in);
   

   fprintf(stderr, "last prime %d got to %d max is %d %d    mod %d %d\n", n, i, Np(maxn), primetest(max),  maxn, primetest(maxn));
  // }

   

   


 
}