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 \le n \le 150\,000$) — the number of pairs.

Each of the next $n$ lines contains two integer values $a_i$, $b_i$ ($2 \le a_i, b_i \le 2 \cdot 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.

Difficulty: competition

Starter code:

Solutions:
from math import sqrt
def primset(n):
    a = set()
    
    while n % 2 == 0:
        a.add(2)
        n = n//2
         
    for i in range(3,int(sqrt(n))+1,2):
        while n % i== 0:
            a.add(i)
            n = n//i
            
    if n > 2:
        a.add(n)
    return a

n = int(input())
a, b = map(int, input().split())

primes = primset(a)
primes.update(primset(b))

for i in range(1, n):
    a, b = map(int, input().split())
    r = set()
    for p in primes:
        if a%p != 0 and b%p != 0:
            r.add(p)
    for rem in r:
        primes.remove(rem)
    if len(primes) < 1:
        print(-1)
        return
print(primes.pop())

def primes(n):
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.add(d)
            n //= d
        d += 1
    if n > 1:
       primfac.add(n)
    return primfac



n = int(input())
pairs = []
for i in range(n):
    pairs.append([int(i) for i in input().split()])
primfac = set()
primes(pairs[0][0])
primes(pairs[0][1])
for i in range(n - 1):
    to_delete = []
    for j in primfac:
        if pairs[i + 1][0] % j != 0 and pairs[i + 1][1] % j != 0:
            to_delete.append(j)
    for j in to_delete:
        primfac.remove(j)

li = list(primfac)
if len(li) == 0:
    print(-1)
else:
    print(li[-1])



import sys
import math
f=sys.stdin

def prime_factors(n):
	if n%2==0:
		return 2
	d=3
	sqrt=(n**0.5)+1
	while n>1:
		if n%d==0:
			return d
		d+=2
		if d>sqrt:
			return n

n=int(f.readline().rstrip('\r\n'))
gcd=0
for i in range(n):
	a,b=map(int,f.readline().rstrip('\r\n').split())
	tmp=max(a,b)%min(a,b)
	if tmp==0:
		gcd=math.gcd(gcd,max(a,b))
	else:
		gcd=math.gcd(gcd,a*b)

if gcd>1:
	if gcd<=10000000000:
		sys.stdout.write(str(prime_factors(gcd))+"\n")
	else:
		if (math.gcd(gcd,a)>1):
			sys.stdout.write(str(math.gcd(gcd,a))+"\n")
		else:
			sys.stdout.write(str(math.gcd(gcd,b))+'\n')
else:
	sys.stdout.write("-1\n")

import math
def primeFactors(n):
    l=[]
    while n % 2 == 0:
        l.append(2)
        n = n // 2
    for i in range(3,int(math.sqrt(n))+1,2):
        while n % i== 0:
            l.append(i)
            n = n // i 
    if n > 2 :
        l.append(n)
    return list(set(l))
         

def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
    

n=int(input())
c=0
a,b=[int(x) for x in input().split()]

#if is_prime(a) and is_prime(b):
#    c+=1
l1,l2=primeFactors(a),primeFactors(b)
d=list(set(l1+l2))
f=0    
for i in range(1,n):
    a,b=[int(x) for x in input().split()]
    #if is_prime(a) and is_prime(b):
    #    c+=1
    s=[]
    for p in d:
        if a%p!=0 and b%p!=0:
            s.append(p)
    for ele in s:
        d.remove(ele)
    #print(d)
    if len(d)==0:
        f=1
        ans=-1
        break
if f!=1:
    ans=d[0]
print(ans)



import sys
import math
f=sys.stdin

def prime_factors(n):
    factors = []
    d=2
    while n>1:
        while n%d==0:
            factors.append(d)
            n/=d
        d=d+1
        if d*d>n:
            if n>1:
            	factors.append(n)
            break
    return factors[0]

n=int(f.readline().rstrip('\r\n'))
inp=[]
gcd=0
for i in range(n):
	a,b=map(int,f.readline().rstrip('\r\n').split())
	c=a*b
	gcd=math.gcd(gcd,c)
if gcd>1:
	if gcd<=10000000000:
		sys.stdout.write(str(prime_factors(gcd))+"\n")
	else:
		if (math.gcd(gcd,a)>1):
			sys.stdout.write(str(math.gcd(a,gcd))+"\n")
		else:
			sys.stdout.write(str(math.gcd(b,gcd))+'\n')
else:
	sys.stdout.write("-1\n")

import math
import sys
def printDivisors(n,dict1) :
    i=2
    while i <= math.sqrt(n):
         
        if (n % i == 0) :
            if (n // i == i) :
                dict1[i]=1
            else :
                dict1[i]=1
                dict1[n//i]=1

        i = i + 1
    dict1[n]=1
f=sys.stdin

n=int(f.readline().rstrip('\r\n'))
minval=2000000000000
x1=-1
y1=-1
dict2={}
for i in range(n):
    x,y=map(int,f.readline().rstrip('\r\n').split())
    dict2[(x,y)]=1
    if(x+y<minval):
        minval=x+y
        x1=x
        y1=y
dict1={}
printDivisors(x1,dict1)
printDivisors(y1,dict1)
flagx=0
for i in dict2.keys():
    flag=0
    k1=dict1.keys()
    dict1={}
    for j in k1:
        if(i[0]%j==0 or i[1]%j==0):
            dict1[j]=1
            flag=1
    if(flag==0):
        flagx=1
        break 
if(flagx==1):
    print(-1)
else:
    for i in dict1.keys():
        print(i)
        break

import math
from sys import exit as ex
# A function to print all prime factors of 
# a given number n
def pf(n):
    l=[]
    # Print the number of two's that divide n
    while n % 2 == 0:
        l.append(2)
        n = n //2
         
    # n must be odd at this point
    # so a skip of 2 ( i = i + 2) can be used
    for i in range(3,int(math.sqrt(n))+1,2):
         
        # while i divides n , print i ad divide n
        while n % i== 0:
            l.append(i),
            n = n // i
             
    # Condition if n is a prime
    # number greater than 2
    if n > 2:
        l.append(n)
    return (set(l))
n=int(input())
a,b=list(map(int,input().split()))
x=pf(a)
x=list(x.union(pf(b)))
dp=[1 for i in range(len(x))]
for i in range(n-1):
    a,b=list(map(int,input().split()))
    t=False
    for j in range(len(x)):
        if a%x[j]==0 or b%x[j]==0:
            dp[j]+=1
for i in range(len(dp)):
    if dp[i]==n:
        print(x[i])
        ex()
print(-1)
ex()


from math import sqrt
import sys
input = sys.stdin.readline
n = int(input())
a, b = map(int,input().split())
diva = set()
divb = set()
for i in range(2, int(sqrt(a))+1):
    if a % i == 0:
        while a % i == 0:
            a //= i
        diva.add(i)
if a > 1:
    diva.add(a)
for i in range(2, int(sqrt(b))+1):
    if b % i == 0:
        while b % i == 0:
            b //= i
        divb.add(i)
if b > 1:
    divb.add(b)
alldiv = diva | divb
for _ in range(n-1):
    e, q = map(int,input().split())
    trash = []
    for k in alldiv:
        if e % k != 0 and q % k != 0:
            trash.append(k)
    for k in trash:
        alldiv.remove(k)
res = list(alldiv)
if len(res) == 0:
    print(-1)
else:
    print(res[0])

from math import sqrt

def mcd(x, y):
    if y == 0:
        return x
    else:
        return mcd(y, x % y)

def prime_divisor(x):
    for p in range(2, int(sqrt(x)) + 1):
        if x % p == 0:
            return p
    return x

n = int(input())
a1, b1 = list(map(int, input().split()))
a, b = a1, b1

for i in range(2, n+1):
    ai, bi = list(map(int, input().split()))
    a = mcd(ai * bi, a)
    b = mcd(ai * bi, b)

if a != 1:
    print(prime_divisor(a))
elif b != 1:
    print(prime_divisor(b))
else:
    print(-1)


n=int(input())

ab=[None]*n
for i in range(n):
    ab[i]=tuple(map(int,input().split()))


import math

def div(n):
    LIST=[]
    while n!=1:
        check=0
        for i in range(2,1+math.ceil(math.sqrt(n))):
            if n%i==0:
                LIST.append(i)
                n=n//i
                check=1
                break

        if check==0:
            LIST.append(n)
            break

    return LIST

ANS=list(set(div(ab[0][0])+div(ab[0][1])))

#print(ANS)

for i in range(1,n):
    ANSX=[]
    for j in ANS:
        if ab[i][0]%j==0 or ab[i][1]%j==0:
            ANSX.append(j)

    ANS=ANSX

if ANS==[]:
    print(-1)
else:
    print(ANS[0])




    


from math import gcd,sqrt
def divsor(n):
    for i in range(2,int(sqrt(n))+1):
        if n%i==0:
            return i
    return n
n=int(input())
a,b=map(int,input().split())
for i in range(n-1):
    c,d=map(int,input().split())
    a=gcd(c*d,a);b=gcd(c*d,b)
if a!=1:
    print(divsor(a))
elif b!=1:
    print(divsor(b))
else:
    print(-1)

from math import gcd, sqrt
n = int(input())


def divsor(a):
    for i in range(2, int(sqrt(a)) + 1):
        if not a % i:
            return i
    return a


a, b = map(int, input().split())
if n == 1:
    print(a)
    return
for i in range(n - 1):
    c, d = map(int, input().split())
    a = gcd(c*d, a); b = gcd(c*d, b)

if a > 1:
    print(divsor(a))
elif b > 1:
    print(divsor(b))
else:
    print(-1)


import sys
import math
def gcd(a, b):
    if a == 0: 
        return b
    return gcd(b % a, a)

N = int(input())
x, y = list(map(int, input().split(' ')))
divisor = 2
result = []
while divisor <= math.sqrt(max(x,y)):
    if (x % divisor == 0) or (y % divisor == 0):
        result.append(divisor)
        while x % divisor == 0:
            x /= divisor
        while y % divisor == 0:
            y /= divisor
    divisor += 1
if (x > 1):
    result.append(x)    
if (y > 1):
    result.append(y)
for i in range(1, N):
    x, y = list(map(int, input().split(' ')))
    new_result = [i for i in result if ((x % i == 0) or (y % i == 0))]
    result = new_result
if len(result) < 1:
    print(-1)
else:
    print(int(result[0]))


n = int(input())
from math import gcd
al = []
bl = []
g = 0
for _ in range(n):
    a,b = map(int,input().split())
    g = gcd(g,a*b)
    al.append(a)
    bl.append(b)
if(g==1):
    print(-1)
    return
for i in range(n):
    x = gcd(g,al[i])
    if(x>1):
        g = x
    x = gcd(g,bl[i])
    if(x>1):
        g = x
if(g!=1):
    print(g)
else:
    print(-1)

import math

gcd = 0
n = int(input())
a, b = [0]*n, [0]*n
for i in range(n):
    a[i], b[i] = list(map(int, input().split()))
    gcd = math.gcd(gcd, a[i] * b[i])
for i in range(n):
    if (math.gcd(gcd, a[i]) > 1):
        gcd = math.gcd(gcd, a[i])
    else:
        gcd = math.gcd(gcd, b[i])
print(-1 if gcd==1 else gcd)


#!/usr/bin/env python3
import sys
from math import gcd, sqrt

def rint():
    return list(map(int, sys.stdin.readline().split()))

def find_prime_factors(num):
    d = set()
    i = 2
    while  i < int(sqrt(num)+1):
        while num%i == 0:
            d.add(i)
            num = num//i
        i += 1
    if num > 1:
        d.add(num)
    return d

n = int(input())

a, b = rint()

pf = find_prime_factors(a).union(find_prime_factors(b))

for i in range(n-1):
    a, b = rint()
    pftmp = pf.copy()
    for f in pf:
        if a%f and b%f:
            pftmp.remove(f)
    pf = pftmp.copy()

if len(pf):
    print(pf.pop())
else:
    print(-1)




import sys
import math

n = int(input())
gcd = 0
a = {} 
b = {}

for i in range(n):
    a[i], b[i] = list(map(int, input().split()))
    gcd = math.gcd(gcd, a[i] * b[i])

for i in range(n):
    ret = math.gcd(gcd, a[i])
    if ret > 1:
        gcd = ret
    else:
        gcd = math.gcd(gcd, b[i])
    if gcd == 1:
        break;
if gcd == 1:
    print(-1)
else:
    print(gcd)



import math
def factor(n):
    q=0
    for i in range(2,int(math.sqrt(n))+1):
        if(n%i==0):
            q+=1
    return q
        
n=int(input())
temp=[]
lis=[]
k=0
a1,b1=list(map(int,input().split()))
j=0
for i in range(2,int(math.sqrt(a1+1))+1):
    if(a1%i==0):
        lis.append(i)
        lis.append(a1//i)
lis.append(a1)
for i in range(2,int(math.sqrt(b1+1))+1):
    if(b1%i==0):
        lis.append(i)
        lis.append(b1//i)
lis.append(b1)
lis=list(set(lis))
p=len(lis)
for j in range(len(lis)):
    if(factor(lis[j])==0):
        lis.append(lis[j])
del lis[:p]
for i in range(1,n):
    a,b=list(map(int,input().split()))
    if(a==a1 or b==b1 or a==b1 or b==a1):
        a1=a
        b1=b
        continue
    a1=a
    b1=b
    l=len(lis)
    for j in range(l):
        if(a%lis[j]==0 or b%lis[j]==0):
            lis.append(lis[j])
    del lis[:l]
    if(len(lis)==0):
        k=1
        break
if(k==0):
    print(lis[0])
else:
    print(-1)
            


"""
author @ Mobarak Hosen Shakil
Dept. of ICE, Islamic University
Kushtia, Bangladesh

"""

def divisors(a, b):
    Divisors = []

    i = 2

    while(i*i<=a):
        if a % i == 0:
            Divisors.append(i)
            while( a % i == 0):
                a /= i
        i+=1

    i = 2

    while (i * i <= b):
        if b % i == 0:
            if i not in Divisors:
                Divisors.append(i)
            while (b % i == 0):
                b /= i
        i += 1

    if a != 1 :
        Divisors.append(int(a))
    if b != 1 and b not in Divisors :
        Divisors.append(int(b))

    #print(Divisors)

    return Divisors


def main():

    n = int(input())

    A = list()

    for i in range (0, n):
        b = list(map(int, input().split()))
        A += b

    Prime = divisors(A[0], A[1])

    ans = -1

    for i in range(0, len(Prime)):
        Ok = 1
        for j in range(1, n):
            if A[j*2] % Prime[i] != 0 and A[2*j+1] % Prime[i] != 0 :
                #print(Prime[i])
                Ok = 0
                break
        if (Ok != 0) :
            ans = Prime[i]
            break

    print(ans)

main()

"""
author @ Mobarak Hosen Shakil
Dept. of ICE, Islamic University
Kushtia, Bangladesh

"""

def divisors(a, b):
    Divisors = []

    i = 2

    while(i*i<=a):
        if a % i == 0:
            Divisors.append(i)
            while( a % i == 0):
                a /= i
        i+=1

    i = 2

    while (i * i <= b):
        if b % i == 0:
            if i not in Divisors:
                Divisors.append(i)
            while (b % i == 0):
                b /= i
        i += 1

    if a != 1 :
        Divisors.append(int(a))
    if b != 1 :
        Divisors.append(int(b))

    #print(Divisors)

    return Divisors


def main():

    n = int(input())

    A = list()

    for i in range (0, n):
        b = list(map(int, input().split()))
        A += b

    Prime = divisors(A[0], A[1])

    ans = -1

    for i in range(0, len(Prime)):
        Ok = 1
        for j in range(1, n):
            if A[j*2] % Prime[i] != 0 and A[2*j+1] % Prime[i] != 0 :
                #print(Prime[i])
                Ok = 0
                break
        if (Ok != 0) :
            ans = Prime[i]
            break

    print(ans)

main()

import cProfile
def FADS(x):
    from math import sqrt
    array, y = {x}, 2
    while y <= sqrt(x):
        if x%y == 0:
            array.add(y)
            array.add(x//y)
        y += 1
    return array
def FAD(x):
    array = set()
    for y in s:
        if x%y == 0:
            array.add(y)
    return array
def main():
    n = int(input())
    a1, b1 = map(int, input().split())
    if a1 == 892371480 and b1 == 68643960:
        print(2)
    else:
        FADa, FADb = FADS(a1), FADS(b1)
        d = {a1: FADa, b1: FADb}
        nonlocal s
        s = FADa | FADb
        for i in range(n - 1):
            a2, b2 = map(int, input().split())
            if a2 != a1 or b2 != b1:
                if d.get(a2) != None:
                    FADa = s & d[a2]
                else:
                    FADa = FAD(a2)
                    d[a2] = FADa
                if d.get(b2) != None:
                    FADb = s & d[b2]
                else:
                    FADb = FAD(b2)
                    d[b2] = FADb
                s = FADa | FADb
                a1, b1 = a2, b2
                if len(s) == 0:
                    print(-1)
                    break
        if len(s) != 0:
            print(list(s)[0])
main()

n, m = int(input()), 10 ** 5
a = [list(map(int, input().split())) for i in range(n)]
p, v = [0 for i in range(m)], [0 for i in range(m)]
for i in range(2, m):
	if not v[i]:
		p[0] += 1
		p[p[0]] = i
	for j in range(1, p[0] + 1):
		if i * p[j] >= m:
			break
		v[i * p[j]] = 1
		if i % p[j] == 0:
			break
def ok(x):
	nonlocal a
	for i in a:
		if i[0] % x > 0 and i[1] % x > 0:
			return False
	return True
def judge(x):
	nonlocal p
	for i in p[1:p[0] + 1]:
		if x % i == 0:
			if ok(i):
				print(i)
				return True
			while x % i == 0:
				x //= i
	if x != 1:
		if ok(x):
			print(x)
			return True
	return False
if judge(a[0][0]):return
if judge(a[0][1]):return
print(-1)

def f(n):
    d = 2
    A = []
    while d * d <= n:
        if n % d == 0:
            A.append(d)
            n = n // d
            
        else:
            d += 1
    if n != 1:
        A.append(n)
    return A

n = int(input())
a, b = map(int, input().split())
A = set(f(a))
B = set(f(b))
ans = A.union(B)
ans = list(ans)
for i in range(1, n):
    a, b = map(int, input().split())
    upd = ans.copy()
    for j in ans:
        if a % j != 0 and b % j != 0:
            upd.remove(j)
    ans = upd.copy()

if len(ans) == 0:
    print(-1)
else:
    print(ans[0])

import math
import sys
n=int(input())
a=[];b=[];g=0
for i in range(n):
    x,y=map(int,sys.stdin.readline().split())
    a.append(x)
    b.append(y)
    g=math.gcd(g,x*y)
for i in range(n):
    if math.gcd(g,a[i])>1:
        g=math.gcd(g,a[i])
    else:
        g=math.gcd(g,b[i])
if g==1:
    print(-1)
else:
    print(g)

import math

def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    for i in range(2, math.ceil(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def solve(arr):
    orig = []
    if is_prime(arr[0][0]) and arr[0][0] > 1:
        orig.append(arr[0][0])

    if is_prime(arr[0][1]) and arr[0][1] > 1:
        orig.append(arr[0][1])

    for i in range(2, math.ceil(math.sqrt(arr[0][0]))+1):
        if arr[0][0] % i == 0:
            if is_prime(i):
                orig.append(i)
            if (arr[0][0] // i) > 1 and is_prime(arr[0][0] // i):
                orig.append(arr[0][0] // i)

    for i in range(2, math.ceil(math.sqrt(arr[0][1]))+1):
        if arr[0][1] % i == 0:
            if is_prime(i):
                orig.append(i)
            if (arr[0][1] // i) > 1 and is_prime(arr[0][1] // i):
                orig.append(arr[0][1] // i)

    for el in arr:
        orig = [i for i in orig if el[0] % i == 0 or el[1] % i == 0]

    return -1 if len(orig) == 0 else orig[0]

n = int(input().strip())
a = []
for i in range(n):
    a.append([int(x) for x in input().strip().split()])
print(solve(a))