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.
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define maxN 1000005
#define rep(i,n) for(int i=0;i<n;i++)
#define refv(i,l,r) for(int i=l;i<r;i++)
#define rerv(i,l,r) for(int i=l;i>r;i--)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll> >
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define inf 10000000000000
#define mod 1000000007
#define MAXN   100001
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl '\n'
using namespace std;
int power(int x, unsigned int y){int res = 1;while (y > 0){ if (y & 1){res = res*x;} y = y>>1;x = x*x;}return res;}
int powermod(int x, unsigned int y, int p){int res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}return res;}
int Mod(int x, int m){ return (x%m+m)%m;}
int spf[MAXN];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}

/*
  1. always check for unintialized vector.

  2. priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > pq; for djikstra

  3. check for constrained properly

  4. 10^8 operations per second

  5. Every even integer greater than 2 can be expressed as the sum of two primes.

  6. odd number can be expresses in sum of two prime number only if (n-2) is prime.

  7. always pass string vector everything  by reference else can get MLe TLE;
  
  8. An even digits of pallindromic number is always divided by 11 euler project 4th question..
  
  If n = 12, the time complexity can be O(n!).
  If n = 25, the time complexity can be O(2n).
  If n = 100, the time complexity can be O(n4).
  If n = 500, the time complexity can be O(n3).
  If n = 10^4, the time complexity can be O(n2).
  If n = 10^6, the time complexity can be O(n log n).
  If n = 10^8, the time complexity can be O(n).
  If n > 10^8, the time complexity can be O(log n) or O(1).

*/


// spf contains smallest prime factor of n
void sieve()
{   spf[1] = 1;
    for (int i=2; i<MAXN; i++)
       spf[i] = i;

    for (int i=4; i<MAXN; i+=2)
        spf[i] = 2;

    for (int i=3; i*i<MAXN; i++)
    {

        if (spf[i] == i)
        {

            for (int j=i*i; j<MAXN; j+=i)
                if (spf[j]==j)
                    spf[j] = i;
        }
    }
}

// A O(log n) function returning primefactorization
vector<int> getFactorization(int x)
{
    vector<int> ret;
    while (x != 1)
    {
        ret.push_back(spf[x]);
        x = x / spf[x];
    }
    return ret;
}

//check if a number is prime   O(sqrt(n))
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}

// print all divisor of a number
void printDivisors(int n)
{

    for (int i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {

            if (n/i == i)
                printf("%d ", i);

            else
                printf("%d %d ", i, n/i);
        }
    }
}

// if range exceeds 10^7 then use below
vector<int> allPrime(int x)
{  vector<int>v;
   for(int i=2;i*i<=x;i++)
    {

    	if(x%i==0)
    	{
    		v.pb(i);
    		while(x%i==0)
				{
					x=x/i;
				}
		}

	}
	if(x>1)v.pb(x);

	return v;
}


// Function to find the nCr
int nCr(int n, int r)
{
    long long p = 1, k = 1;

    if (n - r < r)
        r = n - r;

    if (r != 0) {
        while (r) {
            p *= n;
            k *= r;

            long long m = __gcd(p, k);

            p /= m;
            k /= m;

            n--;
            r--;
        }

	}

    else
        p = 1;

    return p;
}

//dfs
void dfs(vector<int>adj[],vector<int>&vis,int u)
{
	vis[u]=true;
	for(auto x:adj[u])
	{
		if(!vis[x])
		{
			dfs(adj,vis,x);
		}
	}
}

//bfs
void bfs(vector<int>adj[],int u,int n)
{
	queue<int>q;
	q.push(u);
	vector<int>vis(n,false);

	while(!q.empty())
	{
		int v = q.front();
		q.pop();
		vis[v]=true;
		for(auto x:adj[v] )
		{
			if(!vis[x])
			{
				q.push(x);
			}
		}
	}

}

/////  segment tree
int st[1000001];
void updateValue(int arr[], int ss, int se,
                 int index, int value, int node)
{
    if (index < ss || index > se)
    {
        cout << "Invalid Input" << endl;
        return;
    }

    if (ss == se)
    {
        arr[index] = value;
        st[node] = value;
    }
    else {
            int mid =  ss+(se-ss)/2;

            if (index >= ss && index <= mid)
                updateValue(arr,  ss, mid, index,
                            value, 2 * node + 1);
            else
                updateValue(arr,  mid + 1, se,
                            index, value, 2 * node + 2);

            st[node] = max(st[2 * node + 1],
                       st[2 * node + 2]);
    }
    return;
}
int RMQUtil( int ss, int se, int qs, int qe, int index)
{
    if (qs <= ss && qe >= se)
        return st[index];

    if (se < qs || ss > qe)
        return inf;

    int mid = ss+(se-ss)/2;
    return min(RMQUtil( ss, mid, qs, qe, 2*index+1),
                RMQUtil( mid+1, se, qs, qe, 2*index+2));
}


void constructSTUtil(int arr[], int ss, int se,
                                 int si)
{



    if (ss == se)
    {

        st[si] = arr[ss];
        return;

    }

    int mid = ss+(se-ss)/2;
    //cout<<mid<<endl;
    constructSTUtil(arr, ss , mid, 2*si +1);
	constructSTUtil(arr, mid+1, se,2*si +2);
	st[si]  = min(st[2*si+1],st[2*si+2]);

}




int solve()
{


	//do dp here;



}

int32_t main()
{

    fastio;
    int n;
    cin>>n;
    int a[n];
    int b[n];
    rep(i,n)
    {
    	cin>>a[i];
    	cin>>b[i];
	}
	
	map<int,int>p;
	vector<int>v1,v2;
	v1 = allPrime(a[0]);
	v2 = allPrime(b[1]);
	for(int i=0;i<v1.size();i++)
	{
		p[v1[i]]++;
	}
	for(int i=0;i<v2.size();i++)
	{
		if(p.find(v2[i])==p.end())
		{
			p[v2[i]]++;
		}
	}
	int ans = -1;
	
	for(auto x:p)
	{
		int count=0;
		for(int i=0;i<n;i++)
		{
			if(a[i]%x.first==0 || b[i]%x.first==0)
			{
				count++;
			}
		}
		if(count==n)
		{
			cout<<x.first<<endl;
			return 0;
		}
		
	}
	 cout<<"-1\n";
	

  return 0;


}




