Problem: During the research on properties of the greatest common divisor (GCD) of a set of numbers, Ildar, a famous mathematician, introduced a brand new concept of the weakened common divisor (WCD) of a list of pairs of integers.

For a given list of pairs of integers (a_1, b_1), (a_2, b_2), ..., (a_n, b_n) their WCD is arbitrary integer greater than 1, such that it divides at least one element in each pair. WCD may not exist for some lists.

For example, if the list looks like [(12, 15), (25, 18), (10, 24)], then their WCD can be equal to 2, 3, 5 or 6 (each of these numbers is strictly greater than 1 and divides at least one number in each pair).

You're currently pursuing your PhD degree under Ildar's mentorship, and that's why this problem was delegated to you. Your task is to calculate WCD efficiently.

Input

The first line contains a single integer n (1 ≤ n ≤ 150 000) — the number of pairs.

Each of the next n lines contains two integer values a_i, b_i (2 ≤ a_i, b_i ≤ 2 ⋅ 10^9).

Output

Print a single integer — the WCD of the set of pairs. 

If there are multiple possible answers, output any; if there is no answer, print -1.

Examples

Input

3
17 18
15 24
12 15


Output

6

Input

2
10 16
7 17


Output

-1


Input

5
90 108
45 105
75 40
165 175
33 30


Output

5

Note

In the first example the answer is 6 since it divides 18 from the first pair, 24 from the second and 12 from the third ones. Note that other valid answers will also be accepted.

In the second example there are no integers greater than 1 satisfying the conditions.

In the third example one of the possible answers is 5. Note that, for example, 15 is also allowed, but it's not necessary to maximize the output.

Solution (in JAVA):

Solution:






import java.io.*;
import java.util.*;
import java.math.BigInteger; 
import java.lang.*;





public class Main {
    
    
    
    
   static class sort implements Comparator<int[]>
   {
        public int compare(int[] a,int[] b)
        {
            
            return -b[0]+a[0];
        }
   }
   static class sort1 implements Comparator<int[]>
   {
        public int compare(int[] a,int[] b)
        {
            
          return  b[0]-a[0];
        }
   }
   static class sort5 implements Comparator<long[]>
   {
        public int compare(long[] a,long[] b)
        {
            
           double d1,d2;
           d1 = (a[0]+0.00)/(a[1]+0.00);
           d2 = (b[0]+0.00)/(b[1]+0.00);
           //int v = Double.comapre(d2,d1);
           double eph = 0.000000000000001;
           double d = (d2-d1);
          // pr(d1+" "+d2);
           if(d>eph) return 1;
           else if(d<eph) return -1;
           if(a[1]>b[1]) return 1;
           else if(b[1]>a[1]) return -1;
           return 0;
        }
   }
   static class sort11 implements Comparator<double[]>
   {
        public int compare(double[] a,double[] b)
        {
            //if(a[0] == b[0]) return a[1]-b[1];
           if(a[1] < b[1]) return -1;
           else if(a[1] > b[1]) return 1;
           return 0;
        }
   }
   public static String[] F(BufferedReader bf) throws Exception
    {
        return (bf.readLine().split(" "));
    }
    
   public static void pr(PrintWriter out,Object o)
   {
      
    out.println(o.toString());//out.flush();
    
   }
   public static void prW(PrintWriter out,Object o)
   {
      
    out.print(o.toString());//out.flush();
    
   }
   public static int intIn(String st)
   {
      return Integer.parseInt(st);
   }
   
   
    
    public static void pr(Object o)
    {
        System.out.println(o.toString());
    }
    public static void prW(Object o)
    {
        System.out.print(o.toString());
    }
    
   
    public static int inInt(String s)
    {
        return Integer.parseInt(s);
    }
    public static long in(String s)
    {
        return Long.parseLong(s);
    }
 
 
    static int[] toIntArray(String[] m) 
    { 
        int[] p=new int[m.length];
        for(int o=0;o<m.length;o++)
        {
            p[o]= inInt(m[o]);
        }
        return p;
    }
    static double[] toDArray(String[] m) 
    { 
        double[] p=new double[m.length];
        for(int o=0;o<m.length;o++)
        {
            p[o]= Double.parseDouble(m[o]);
        }
        return p;
    }
    static long[] toLArray(String[] m) 
    { 
       long[] p=new long[m.length];
        for(int o=0;o<m.length;o++)
        {
            p[o]= in(m[o]);
        }
        return p;
    }
    
    static int[][] di={{0,1},{1,0},{0,-1},{-1,0}};
    static int[] dir = {4,3,2,-4,-3,-2};
    
     static long gcd(long a, long b)
        {
          if (b == 0)
            return a;
          return gcd(b, a % b); 
        }
        static long Gp(long l,long b,long lcm)
        {
            long c1,c2;
                c1 = (l/lcm);
                long sum=0l;
                sum += (c1-1l)*(b);
                long las = (l/lcm)*lcm;
                sum += Math.min(l-las+1l,b);
                return sum;
        }
        static long pow(long x, long y, long p)
      {
        if(y == 0) return 1l;
        long res = 1; // Initialize result
     
        x = x % p; // Update x if it is more than or
        // equal to p
     
        if (x == 0)
          return 0l; // In case x is divisible by p;
     
        while (y > 0)
        {
     
          // If y is odd, multiply x with result
          if ((y & 1) != 0)
            res = (res * x) % p;
     
          // y must be even now
          y = y >> 1; // y = y/2
          x = (x * x) % p;
        }
        return res;
      }
    
    public static long F(int a,int b)
    {
         return 462161773423l*(a+0l) + 4549834777463l*(b+0l);
    }
    static int nCr(int n, int r, int p)
    {
        if (r > n - r)
            r = n - r;
 
        // The array C is going to store last
        // row of pascal triangle at the end.
        // And last entry of last row is nCr
        int C[] = new int[r + 1];
 
        C[0] = 1; // Top row of Pascal Triangle
 
        // One by constructs remaining rows of Pascal
        // Triangle from top to bottom
        for (int i = 1; i <= n; i++) {
 
            // Fill entries of current row using previous
            // row values
            for (int j = Math.min(i, r); j > 0; j--)
 
                // nCj = (n-1)Cj + (n-1)C(j-1);
                C[j] = (C[j] + C[j - 1]) % p;
        }
        return C[r];
    }
    // F(o,-1,tm,vis,par,o,mat);
   public static int log(int x)
   {
       boolean bol = true;

       if(((x-1)&x) == 0) bol=false;

       int c=0;
       while(x > 0)
       {
        x=(x/2);
        c++;
       }

       if(!bol) c--;
       return c;

   }

   public static int F(int[] arr,int j,int x,int n)
   {

    if(j>=n) return 0;
    if(j == (n-1)) return 0;
    boolean bt = false;
       int i = j;

       while(i<n && arr[i]<= x)
       {
          i++;
       }
       int k = j;
       //if(i == n) return 0;
       i--;
       while(k<i)
       {
          if(arr[k]>arr[k+1]) return -10000000;
          k++;
       }
       k = i+1;
       while(k<n)
       {
            if(arr[k] < x ) bt=true;
            k++;
       }

       k = j;
       boolean bol = true;
       while(k<(n-1))
       {
          if(arr[k]>arr[k+1]) 
          {
            bol=false;break;
          }

          k = k+1;
       }
       if(bol) return 0;

       int tem = arr[i+1];
       arr[i+1] = x;
       //x=tem;
       int sum;
       if(!bt)
        sum =  1 + F(arr,i+2,tem,n);
        else sum=-10000000;
     // System.out.println(sum+" "+j+" "+x);
       return sum;

   }
   static class sor implements Comparator<long[]>
   {
      public int compare(long[] a,long[] b)
      {
         if(a[0] == b[0])
         {
            if(a[1] < b[1]) return -1;
            return 1;
         }
         if(a[0] > b[0]) return 1;
         return -1;
      }
   }

   public static void F(int i,int[] vis,int v,List<Set<Integer>> list,TreeMap<Integer,Integer> tm,int[] arr)
   {
        vis[i] = v;
        if(tm.containsKey(arr[i])) tm.put(arr[i],tm.get(arr[i])+1);
        else tm.put(arr[i],1);
        for(int r : list.get(i))
        {
            if(vis[r] == 0)
            {
                F(r,vis,v,list,tm,arr);
            }
        }
   }
    static long ncr(int n, int r)
    {
 
        // p holds the value of n*(n-1)*(n-2)...,
        // k holds the value of r*(r-1)...
        long p = 1, k = 1;
        if(n<r) return 0l;
 
        // C(n, r) == C(n, n-r),
        // choosing the smaller value
        if (n - r < r) {
            r = n - r;
        }
 
        if (r != 0) {
            while (r > 0) {
                p *= n;
                k *= r;
 
                // gcd of p, k
                long m = __gcd(p, k);
 
                // dividing by gcd, to simplify
                // product division by their gcd
                // saves from the overflow
                p /= m;
                k /= m;
 
                n--;
                r--;
            }
 
            // k should be simplified to 1
            // as C(n, r) is a natural number
            // (denominator should be 1 ) .
        }
        else {
            p = 1;
        }
 
        // if our approach is correct p = ans and k =1
        return p;
    }
 
    static long __gcd(long n1, long n2)
    {

        if(n1==0l) return n2;
        if(n2==0l) return n1;
        if(n1==1l || n2==1l) return 1l;
       // long gcd = 1;
        if(n1 == n2)  return n1;
        if(n1>n2) return __gcd(n1%n2,n2);
        return __gcd(n1,n2%n1);
        
    }
  
    public static int F(int i,int j,List<List<Integer>> list,int[] tot,boolean[] right)
    {
      int c=0;

        if(list.get(i).size() == 1)
        {
            right[i]=true;
            c++;
        }
        

        for(int x : list.get(i))
        {
            if(x==j) continue;

            c += F(x,i,list,tot,right);
        }

        tot[i]=c;return c;

    }

    public static void main (String[] args) throws Exception {
        
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);;;
        
        //int[] map=new int[1000001];
      
       int yy=1;//inInt(bf.readLine());
       


        
        for(int w=0;w<yy;w++)
        {
            // String str = bf.readLine();
          out.flush();
         
            String[] xlp = bf.readLine().split(" ");;;;;;
            //String st = bf.readLine();
         int n;//boolean bol=false;
           long m;//long a,b,c;
           int ioo;
           long  k;//pr(out,"vbc");
         n=inInt(xlp[0]);//m=in(xlp[1]);//k=in(xlp[2]);//t=inInt(xlp[3]);

         long[][] arr = new long[n][2];


         for(int o=0;o<n;o++)
         {
            arr[o] =toLArray(F(bf));

         }

         long res=0l;
       // pr(out,__gcd((1999999973l*1999999943l),0l));
         for(int o=0;o<n;o++)
         {
            long a = (arr[o][0]*arr[o][1]);
            //pr(out,a);
            //long g = __gcd(arr[o][0],arr[o][1]);
            
            //a =(a/g);
            res = __gcd(res,a);
            //pr(out,res+" "+a);
         }
         //pr(out,res);

         if(res == 1l) pr(out,-1);
         else{
         long r = __gcd(res,arr[0][0]);
         if(r==1l) r = __gcd(res,arr[0][1]);
         int rt = (int)(Math.sqrt(r)+1);
         for(int o=2;o<=rt;o++)
         {
             if((r%o) == 0)
             {
                  r=o;break;
             }
         }

         pr(out,r);}

         




      

         
         
         



         
         
   }
    out.close();
   bf.close();
}}


/*
2
1999999973 1999999943
1999999973 1999999943

Kickstart
 String rp;
            rp = "Case #"+(w+1)+": "+(n-ans)+" ";
static int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};

static class SegmentTreeRMQ 
    { 
    int st[]; 
    int minVal(int x, int y) { 
        return (x > y) ? x : y; 
    } 
  
    
    int getMid(int s, int e) { 
        return s + (e - s) / 2; 
    } 
  
    
    int RMQUtil(int ss, int se, int qs, int qe, int index) 
    { 
        
        if (qs <= ss && qe >= se) 
            return st[index]; 
  
        // If segment of this node is outside the given range 
        if (se < qs || ss > qe) 
            return Integer.MIN_VALUE; 
  
        // If a part of this segment overlaps with the given range 
        int mid = getMid(ss, se); 
        return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1), 
                RMQUtil(mid + 1, se, qs, qe, 2 * index + 2)); 
    } 
  
    // Return minimum of elements in range from index qs (query 
    // start) to qe (query end).  It mainly uses RMQUtil() 
    int RMQ(int n, int qs, int qe) 
    { 
        // Check for erroneous input values 
        
  
        return RMQUtil(0, n - 1, qs, qe, 0); 
    } 
  
    // A recursive function that constructs Segment Tree for 
    // array[ss..se]. si is index of current node in segment tree st 
    int constructSTUtil(int arr[], int ss, int se, int si) 
    { 
        // If there is one element in array, store it in current 
        //  node of segment tree and return 
        if (ss == se) { 
            st[si] = arr[ss]; 
            return arr[ss]; 
        } 
  
        // If there are more than one elements, then recur for left and 
        // right subtrees and store the minimum of two values in this node 
        int mid = getMid(ss, se); 
        st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1), 
                constructSTUtil(arr, mid + 1, se, si * 2 + 2)); 
        return st[si]; 
    } 
  
    
    void con(int arr[]) 
    { 
        // Allocate memory for segment tree 
  
        //Height of segment tree 
        int n = (arr.length);
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
  
        //Maximum size of segment tree 
        int max_size = 2 * (int) Math.pow(2, x) - 1; 
        st = new int[max_size]; // allocate memory 
  
        // Fill the allocated memory st 
        constructSTUtil(arr, 0, n - 1, 0); 
    }
    }
     static class DSU {
    
    int[] p;int[] sz;int op;int c;;
    int[] last;
    public void G(int n)
    {
        last=new int[n];
        p=new int[n];
        sz=new int[n];c=n;
        op=n;
        for(int h=0;h<n;h++)
        {
            sz[h]=1;p[h]=h;
            last[h]=h;
        }
    }
    public int find(int x)
    {
        int y=x;
        while(x!=p[x]) x=p[x];
        while(y!=p[y])
        {
            int tem=p[y];
            p[y]=x;y=tem;
        }
        return p[y];
    }
    public void union(int a,int b)
    {
        int x,y;
        x=find(a);y=find(b);
        if(x==y) return;
        if(sz[x]>sz[y])
        {
            p[y] = x;
            sz[x]+=sz[y];
            last[x]=Math.max(last[x],last[y]);
        }
        else
        {
            p[x]=y;sz[y]+=sz[x];
            last[y]=Math.max(last[y],last[x]);
        }
        c--;
        
    }}

    static long pow(long x, long y, long p)
      {
        long res = 1; // Initialize result
     
        x = x % p; // Update x if it is more than or
        // equal to p
     
        if (x == 0)
          return 0l; // In case x is divisible by p;
     
        while (y > 0)
        {
     
          // If y is odd, multiply x with result
          if ((y & 1) != 0)
            res = (res * x) % p;
     
          // y must be even now
          y = y >> 1; // y = y/2
          x = (x * x) % p;
        }
        return res;
      }
      static long gcd(long a, long b)
        {
          if (b == 0)
            return a;
          return gcd(b, a % b); 
        }
        static int gcd(int a, int b,int o)
        {
          if (b == 0)
            return a;
          return gcd(b, a % b,o); 
        }

Geometric median

public static double F(double[] x,double[] w)
    {
        double d1,d2;
        double S=0.00;
        for(double dp : w) S += dp;
        int k = 0;
        double sum = S - w[0]; // sum is the total weight of all `x[i] > x[k]`

        while(sum > S/2)
        {
            ++k;
            sum -= w[k];
        }
        d1=x[k];
        return d1;
        k = w.length-1;
       sum = S - w[k]; // sum is the total weight of all `x[i] > x[k]`

        while(sum > S/2)
        {
            --k;
            sum -= w[k];
        }
        d2=x[k];
        return new double[]{d1,d2};
    }
*/