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.
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.*;
import java.io.*;
import java.math.*;
public class Main
{
    public static long pow(long a, long b)
    {
        long result=1;
        while(b>0)
        {
            if (b % 2 != 0)
            {
                result=(result*a);
                b--;
            } 
            a=(a*a);
            b /= 2;
        }   
                return result;
    }
    public static BigInteger fact(long num)
    {
                BigInteger fact=new BigInteger("1");
                int i=0;
                for(i=1; i<=num; i++)
                {
                    BigInteger bg=BigInteger.valueOf(i);
                    fact=fact.multiply(bg);
                }
                return fact;
            }
            public static long gcd(long a, long b)
            {
                if (a == 0)
                    return b;
                return gcd(b%a, a);
            }
            
            public static long lcm(int a,int b)
            {
                return a * (b / gcd(a, b));
            }
            public static long sum(int h)
            {
                return (h*(h+1)/2);
            }
		/*	public static void dfs(int parent,boolean[] visited)
			{
				ArrayList<Integer> arr=new ArrayList<Integer>();
				arr=graph.get(parent);
				visited[parent]=true;
				storing1[parent]=count++;
				for(int i=0;i<arr.size();i++)
				{
					int num=arr.get(i);
					if(visited[num]==false)
					{
						dfs(num,visited);
					}
				}
				storing2[parent]=count;
			}
			static int count=0;
			static int[] storing1;
			static int[] storing2;
			static ArrayList<ArrayList<Integer>> graph;
		*/	public static void main(String args[])throws IOException
            {
                InputReader in=new InputReader(System.in);
        		OutputWriter out=new OutputWriter(System.out);
        	//	long a=pow(26,1000000005);
        	//    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        	    ArrayList<Integer> ar=new ArrayList<>();
				ArrayList<Integer> ar1=new ArrayList<>();
				TreeSet<Integer> ts=new TreeSet<>();
				TreeSet<Integer> ts1=new TreeSet<>();
				HashMap<Long,Integer> hash=new HashMap<Long,Integer>();
				int n=in.readInt();
				long[] a= new long[n];
				long[] b=new long[n];
				for(int i=0;i<n;i++)
				{
					String s1=in.readString();
					a[i]=Long.parseLong(s1);
					s1=in.readString();
					b[i]=Long.parseLong(s1);
				}
				long[] c=new long[4];
				long gcd3=0,gcd1=0,gcd2=0,gcd4=0;
				for(int i=0;i<n-1;i++)
				{
					if(i==0)
					{
						gcd1=gcd(a[i],a[i+1]);
						gcd2=gcd(a[i],b[i+1]);
						gcd3=gcd(b[i],a[i+1]);
						gcd4=gcd(b[i],b[i+1]);
						c[0]=gcd1;
						c[1]=gcd2;
						c[2]=gcd3;
						c[3]=gcd4;
						for(int j=0;j<4;j++)
						{
							if(hash.get(c[j])==null)
							{
								hash.put(c[j],1);
							}
							else
							{
								hash.put(c[j],hash.get(c[j])+1);
							}
						}
					}
					else
					{
						gcd1=gcd(a[i],a[i+1]);
						gcd2=gcd(a[i],b[i+1]);
						gcd3=gcd(b[i],a[i+1]);
						gcd4=gcd(b[i],b[i+1]);
						c[0]=gcd1;
						c[1]=gcd2;
						c[2]=gcd3;
						c[3]=gcd4;
						for(int j=0;j<4;j++)
						{
							if(hash.get(c[j])==null)
							{
								hash.put(c[j],1);
							}
							else
							{
								hash.put(c[j],hash.get(c[j])+1);
							}
						}
					}
				//	System.out.println(c[0]+" love "+hash.get(c[0]));
					
				//	System.out.println(c[1]+" love "+hash.get(c[1]));
					
				//	System.out.println(c[2]+" love "+hash.get(c[2]));
					
				//	System.out.println(c[3]+" love "+hash.get(c[3]));
				}
				
				Map<Long, Integer> map = sortByValues(hash); 
				//System.out.println("After Sorting:");
				Set set2 = map.entrySet();
				Iterator iterator2 = set2.iterator();
				long num1=0,num=0;
				while(iterator2.hasNext())
				{
					Map.Entry me2 = (Map.Entry)iterator2.next();
					num=(Integer)me2.getValue();
					num1=(Long)me2.getKey();
					break;
				//	System.out.print(me2.getKey() + ": ");
				//	System.out.println(me2.getValue());
				}
				if(num==n && num1!=1)
				{
					System.out.println(num1);	
				}
				else
				{
					System.out.println("-1");
				}
            }
			private static HashMap sortByValues(HashMap map)
			{ 
				List list = new LinkedList(map.entrySet());
				// Defined Custom Comparator here
				Collections.sort(list, new Comparator() {
					public int compare(Object o1, Object o2) {
					return ((Comparable) ((Map.Entry) (o2)).getValue()).compareTo(((Map.Entry) (o1)).getValue());
            }
       });

       // Here I am copying the sorted list in HashMap
       // using LinkedHashMap to preserve the insertion order
       HashMap sortedHashMap = new LinkedHashMap();
       for (Iterator it = list.iterator(); it.hasNext();) {
              Map.Entry entry = (Map.Entry) it.next();
              sortedHashMap.put(entry.getKey(), entry.getValue());
       } 
       return sortedHashMap;
  }
        }
        
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
        class InputReader {
        	 
        	private InputStream stream;
        	private byte[] buf = new byte[1024];
        	private int curChar;
        	private int numChars;
        	private SpaceCharFilter filter;
         
        	public InputReader(InputStream stream) {
        		this.stream = stream;
        	}
         
        	public int read() {
        		if (numChars== -1)
        			throw new InputMismatchException();
        		if (curChar >= numChars) {
        			curChar = 0;
        			try {
        				numChars = stream.read(buf);
        			} catch (IOException e) {
        				throw new InputMismatchException();
        			}
        			if (numChars <= 0)
        				return -1;
        		}
        		return buf[curChar++];
        	}
         
        	public int readInt() {
        		int c = read();
        		while (isSpaceChar(c))
        			c = read();
        		int sgn = 1;
        		if (c == '-') {
        			sgn = -1;
        			c = read();
        		}
        		int res = 0;
        		do {
        			if (c < '0' || c > '9')
        				throw new InputMismatchException();
        			res *= 10;
        			res += c - '0';
        			c = read();
        		} while (!isSpaceChar(c));
        		return res * sgn;
        	}
         
        	public String readString() {
        		int c = read();
        		while (isSpaceChar(c))
        			c = read();
        		StringBuilder res = new StringBuilder();
        		do {
        			res.appendCodePoint(c);
        			c = read();
        		} while (!isSpaceChar(c));
        		return res.toString();
        	}
         
        	public boolean isSpaceChar(int c) {
        		if (filter != null)
        			return filter.isSpaceChar(c);
        		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        	}
         
        	public String next() {
        		return readString();
        	}
         
        	public interface SpaceCharFilter {
        		public boolean isSpaceChar(int ch);
        	}
        }
         
        class OutputWriter {
        	private final PrintWriter writer;
         
        	public OutputWriter(OutputStream outputStream) {
        		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        	}
         
        	public OutputWriter(Writer writer) {
        		this.writer = new PrintWriter(writer);
        	}
         
        	public void print(Object...objects) {
        		for (int i = 0; i < objects.length; i++) {
        			if (i != 0)
        				writer.print(' ');
        			writer.print(objects[i]);
        		}
        	}
         
        	public void printLine(Object...objects) {
        		print(objects);
        		writer.println();
        	}
         
        	public void close() {
        		writer.close();
        	}
         
        	public void flush() {
        		writer.flush();
        	}
         
        	}
         
            class IOUtils {
         
        	public static int[] readIntArray(InputReader in, int size) {
        		int[] array = new int[size];
        		for (int i = 0; i < size; i++)
        			array[i] = in.readInt();
        		return array;
        	}
         
        	} 