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.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Number theory

Complete search

Greedy algorithms


Solutions:
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)


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])


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))
	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:
				Ok = 0
				break
		if Ok != 0:
			ans = Prime[i]
			break
	print(ans)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
(a, b) = map(int, input().split())
s = set()
for i in range(2, int(a ** 0.5) + 1):
	if a % i == 0:
		s.add(i)
	while a % i == 0:
		a //= i
if a != 1:
	s.add(a)
a = b
for i in range(2, int(a ** 0.5) + 1):
	if a % i == 0:
		s.add(i)
	while a % i == 0:
		a //= i
if a != 1:
	s.add(a)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	y = set()
	for j in s:
		if a % j != 0 and b % j != 0:
			y.add(j)
	for j in y:
		s.remove(j)
if len(s) == 0:
	print(-1)
else:
	for j in s:
		print(j)
		break


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)


import sys
input = sys.stdin.readline

def inpl():
	return list(map(int, input().split()))

def gcd(x, y):
	if x % y == 0:
		return y
	else:
		(x, y) = (y, x % y)
		return gcd(x, y)
N = int(input())
nums = []
g = 0
for i in range(N):
	(a, b) = inpl()
	nums.append([a, b])
	g = gcd(g, a * b)
for i in range(N):
	(ga, gb) = (gcd(g, nums[i][0]), gcd(g, nums[i][1]))
	g = max(ga, gb)
if g == 1:
	g = -1
print(g)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

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

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import gcd

def main():
	n = N()
	lst = -1
	rec = []
	for _ in range(n):
		(a, b) = RL()
		rec.append((a, b))
		g = gcd(a, b)
		lcm = a * b // g
		if lst != -1:
			lst = gcd(lst, lcm)
		else:
			lst = lcm
	for (a, b) in rec:
		now = gcd(lst, a)
		if now > 1:
			lst = now
		else:
			lst = gcd(lst, b)
	print(lst if lst != 1 else -1)
main()


import math

def divisors(n):
	divs = []
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			divs.extend([i, n // i])
	divs.extend([n])
	return set(divs)
n = int(input())
(a, b) = map(int, input().split())
divs = divisors(a).union(divisors(b))
temp = sorted(list(divs))
divs.clear()
for v in temp:
	insert = True
	for item in divs:
		if v % item == 0:
			insert = False
			break
	if insert:
		divs.add(v)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	temp_divs = set()
	for v in divs:
		if a % v == 0:
			temp_divs.add(v)
		if b % v == 0:
			temp_divs.add(v)
	divs = temp_divs
	if len(divs) == 0:
		break
if len(divs) == 0:
	print(-1)
else:
	print(divs.pop())


import os, sys
from io import BytesIO, IOBase
from math import sqrt, ceil, gcd
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def dtb(n):
	return bin(n).replace('0b', '')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def lcm(a, b):
	return a * b // gcd(a, b)
n = int(input())
ans = 0
(a, b) = (0, 0)
for _ in range(n):
	(a, b) = map(int, input().split())
	ans = gcd(ans, lcm(a, b))
if ans <= 1:
	print(-1)
else:
	ck = 0
	i = 2
	t = sqrt(a)
	while i < a and i <= t:
		if a % i == 0:
			if ans % i == 0:
				ck = i
				break
			while a % i == 0:
				a //= i
		i += 1
	if not ck:
		if ans % a == 0:
			ck = a
	if not ck:
		i = 2
		t = sqrt(b)
		while i < b and i <= t:
			if b % i == 0:
				if ans % i == 0:
					ck = i
					break
				while b % i == 0:
					b //= i
			i += 1
		if not ck:
			if ans % b == 0:
				ck = b
	print(ck)


n = int(input())
l1 = []
l2 = []
for i in range(n):
	(a, b) = map(int, input().split())
	l1.append(a)
	l2.append(b)
L = []
j = 2
a = l1[0]
b = l2[0]
while j * j <= a:
	if a % j == 0:
		while a % j == 0:
			a = a // j
		L.append(j)
	j = j + 1
if a > 1:
	L.append(a)
j = 2
while j * j <= b:
	if b % j == 0:
		while b % j == 0:
			b = b // j
		L.append(j)
	j = j + 1
if b > 1:
	L.append(b)
L = list(set(L))
g = 0
for j in L:
	f = 0
	for k in range(1, n):
		if l1[k] % j != 0 and l2[k] % j != 0:
			f = 1
			break
	if f == 0:
		g = 1
		print(j)
		break
if g == 0:
	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]))


from math import sqrt

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def f(a):
	for i in range(2, int(sqrt(a)) + 1, 1):
		if a % i == 0:
			return i
	return a
n = int(input())
(x, y) = map(int, input().split())
if n == 1:
	print(x)
else:
	a = x * y
	for i in range(n - 2):
		(x, y) = map(int, input().split())
		a = gcd(a, x * y)
	(x, y) = map(int, input().split())
	x = gcd(a, x)
	y = gcd(a, y)
	if x == 1 and y == 1:
		print(-1)
	elif x > 1:
		print(f(x))
	else:
		print(f(y))


import math
from sys import exit as ex

def pf(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 set(l)
n = int(input())
(a, b) = 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) = 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()


n = int(input())
(x, y) = map(int, input().split())
primes = list()
arr = []
for i in [x, y]:
	k = 2
	while k * k <= i:
		if i % k == 0:
			while i % k == 0:
				i //= k
			primes.append(k)
		k += 1
	if i > 1:
		primes.append(i)
for _ in range(n - 1):
	arr.append(list(map(int, input().split())))
for p in primes:
	flag = True
	for (x, y) in arr:
		if x % p != 0 and y % p != 0:
			flag = False
			break
	if flag:
		print(p)
		break
else:
	print(-1)


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)
	exit(0)
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)


primes = set()
(ar, br) = ([0] * 150001, [0] * 150001)

def gen(num):
	i = 2
	while i * i <= num:
		if num % i == 0:
			while num % i == 0:
				num //= i
			primes.add(i)
		i += 1
	if num > 1:
		primes.add(num)
n = int(input())
for i in range(1, n + 1):
	(ar[i], br[i]) = map(int, input().split())
gen(ar[1])
gen(br[1])
for p in primes:
	ok = 1
	for i in range(2, n + 1):
		if ar[i] % p != 0 and br[i] % p != 0:
			ok = 0
			break
	if ok:
		print(p)
		exit(0)
print(-1)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
test = int(input())
list = [tuple(map(int, input().split())) for i in range(test)]
ans = 0
for (a, b) in list:
	ans = gcd(a * b, ans)
for (a, b) in list:
	if gcd(ans, b) != 1:
		ans = gcd(ans, b)
	else:
		ans = gcd(ans, a)
if ans == 1:
	print(-1)
else:
	print(ans)


from math import gcd
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
x = 0
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = gcd(x, a * b)
if x == 1:
	print(-1)
else:
	if gcd(x, a) != 1:
		x = gcd(x, a)
	else:
		x = gcd(x, b)
	n = int(x ** 0.5)
	mark = [False] * (n + 1)
	mark[0] = mark[1] = True
	primes = set()
	for i in range(2, n + 1):
		if mark[i] == False:
			if x % i == 0:
				print(i)
				break
			primes.add(i)
			for j in range(i + i, n + 1, i):
				mark[j] = True
	else:
		print(x)


import sys
from math import gcd, sqrt

def rint():
	return 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
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')
	elif 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 sys
input = sys.stdin.readline

def check(f):
	for (Ai, Bi) in AB:
		if Ai % f != 0 and Bi % f != 0:
			return False
	return True

def factorize(n):
	factors = []
	for i in range(2, int(n ** 0.5) + 1):
		cnt = 0
		while n % i == 0:
			n //= i
			cnt += 1
		if cnt > 0:
			factors.append((i, cnt))
	if n > 1:
		factors.append((n, 1))
	return factors
n = int(input())
AB = [tuple(map(int, input().split())) for _ in range(n)]
cands = factorize(AB[0][0]) + factorize(AB[0][1])
for (f, _) in cands:
	if check(f):
		print(f)
		exit()
print(-1)


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()


def findPF(n, pf):
	if n <= 1:
		return
	i = 2
	while i * i <= n:
		if n % i == 0:
			pf.add(i)
			while n > 1 and n % i == 0:
				n = n // i
		i += 1
	if n > 1:
		pf.add(n)
n = int(input())
(a, b) = map(int, input().split())
pf = set()
findPF(a, pf)
findPF(b, pf)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	for s in list(pf):
		if a % s != 0 and b % s != 0:
			pf.remove(s)
if len(pf) >= 1:
	print(pf.pop())
else:
	print(-1)


from sys import stdin
from operator import mul

def main():
	input()
	pp = set()
	data = set(stdin.read().splitlines())
	for a in set(map(int, min(data, key=len).split())):
		for p in (2, 3, 5):
			if not a % p:
				pp.add(p)
				while not a % p:
					a //= p
		p = 7
		while a >= p * p:
			for s in (4, 2, 4, 2, 4, 6, 2, 6):
				pp.add(p)
				while not a % p:
					a //= p
				p += s
		if a > 1:
			pp.add(a)
	for s in data:
		a = mul(*map(int, s.split()))
		pp = [p for p in pp if not a % p]
		if not pp:
			print(-1)
			return
	print(max(pp))
main()


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])))
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 sys import stdin

def main():
	input()
	pp = set()
	for a in map(int, set(input().split())):
		for p in (2, 3, 5):
			if not a % p:
				pp.add(p)
				while not a % p:
					a //= p
		p = 7
		while a >= p * p:
			for s in (4, 2, 4, 2, 4, 6, 2, 6):
				pp.add(p)
				while not a % p:
					a //= p
				p += s
		if a > 1:
			pp.add(a)
	for s in set(stdin.read().splitlines()):
		(a, b) = map(int, s.split())
		a *= b
		pp = [p for p in pp if not a % p]
		if not pp:
			print(-1)
			return
	print(max(pp))
main()


import sys
input = sys.stdin.buffer.readline

def is_prime(x):
	i = 2
	global s
	p = x
	while i * i <= x:
		flag = 0
		while p % i == 0:
			p //= i
			flag = 1
		if flag == 1:
			s.add(i)
		i += 1
	if p > 1:
		s.add(p)
n = int(input())
s = set()
lst = []
for i in range(n):
	(a, b) = map(int, input().split())
	lst.append([a, b])
is_prime(lst[0][0])
is_prime(lst[0][1])
r = set()
for i in range(1, n):
	l = lst[i][0]
	rr = lst[i][1]
	r = set()
	for j in s:
		if l % j == 0:
			r.add(j)
	for j in s:
		if rr % j == 0:
			r.add(j)
	s = r
if len(s) == 0:
	print(-1)
else:
	for i in s:
		print(i)
		break


import math
n = int(input())
lis = []
for i in range(n):
	lis.append(list(map(int, input().split())))
a = lis[0][0]
a1 = lis[0][1]
se = set()

def fac(a):
	z = int(math.sqrt(a))
	while a:
		if a == 2 or a == 3:
			se.add(a)
			break
		for i in range(2, z + 1):
			if a % i == 0:
				se.add(i)
				a = a // i
				z = int(math.sqrt(a))
				break
		else:
			if a != 1:
				se.add(a)
				a = 0
flag = 0
fac(a)
fac(a1)
for i in se:
	for j in lis:
		if j[0] % i != 0 and j[1] % i != 0:
			break
	else:
		flag = 1
		print(i)
		break
if flag == 0:
	print(-1)


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)


import bisect
from itertools import accumulate, count
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return sorted(fac)

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
ans = []
for i in range(n):
	(a, b) = map(int, input().split())
	ans.append([a, b])
f1 = primefactors(ans[0][0])
f2 = primefactors(ans[0][1])
f1 = f1 + f2
f1 = set(f1)
for i in f1:
	f = 0
	for j in range(0, len(ans)):
		if ans[j][0] % i == 0 or ans[j][1] % i == 0:
			pass
		else:
			f = 1
			break
	if f == 0:
		print(i)
		exit()
print(-1)


n = int(input())
ar = []
(a, b) = map(int, input().split())
num = a ** 0.5 + 2
i = 2
while i < num:
	if a % i == 0:
		ar += [i]
	while a % i == 0:
		a //= i
	i += 1
num = b ** 0.5 + 2
i = 2
while i < num:
	if b % i == 0:
		ar += [i]
	while b % i == 0:
		b //= i
	i += 1
if a != 1:
	ar += [a]
if b != 1:
	ar += [b]
for i in range(1, n):
	(a, b) = map(int, input().split())
	ar2 = []
	for j in ar:
		if a % j == 0 or b % j == 0:
			ar2 += [j]
	ar = ar2
if len(ar) == 0:
	print(-1)
else:
	print(ar[0])


from sys import stdin
from math import gcd

def prime_factors(x):

	def add_n_div(n, k, factor):
		if n % k == 0:
			factor.add(k)
			while n % k == 0:
				n //= k
		return (n, factor)
	ans = set()
	(x, ans) = add_n_div(x, 2, ans)
	i = 3
	while i * i <= x:
		(x, ans) = add_n_div(x, i, ans)
		i = i + 2
	if x != 1:
		ans.add(x)
	return ans
input = stdin.readline
b = [[*map(int, input().split())] for x in range(int(input()))]
n = len(b)
if n == 1:
	print(b[0][0])
else:
	f = prime_factors(b[0][0])
	f.update(prime_factors(b[0][1]))
	for i in b:
		f = {x for x in f if i[0] % x == 0 or i[1] % x == 0}
	if len(f) == 0:
		print(-1)
	else:
		for i in f:
			print(i)
			break


import math
N = int(input())
(a, b) = map(int, input().split())

def factorize(val):
	fs = set()
	i = 2
	while i <= int(math.sqrt(val)) + 1:
		if val % i == 0:
			fs.add(i)
			while val % i == 0:
				val //= i
		i += 1
	if val > 1:
		fs.add(val)
	return fs
factors = factorize(a) | factorize(b)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	factors = {v for v in factors if a % v == 0 or b % v == 0}
	if not factors:
		print(-1)
		exit(0)
print(min(factors))


import math
import sys
n = int(input())
a = []
b = []
g = 0
for i in range(n):
	(p, q) = map(int, sys.stdin.readline().split())
	a.append(p)
	b.append(q)
	g = math.gcd(g, p * q)
	if 1 == g:
		exit(print('-1'))
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])
print(g)


from sys import stdin
from math import gcd
input = stdin.readline
n = int(input())
ab = [list(map(int, input().split())) for i in range(n)]
z = ab[0][0] * ab[0][1]
for (a, b) in ab:
	z = gcd(z, a * b)
for (a, b) in ab:
	if gcd(z, a) > 1:
		z = gcd(z, a)
	else:
		z = gcd(z, b)
print(z if z != 1 else -1)


from math import sqrt
pairs = []
n = int(input())
for _ in range(n):
	(a, b) = list(map(int, input().split()))
	pairs.append((a, b))

def PF(n, set):
	for i in range(2, int(sqrt(n)) + 1, 1):
		if n % i == 0:
			set.add(i)
		while n % i == 0:
			n /= i
	if n >= 2:
		set.add(n)
prime = set()
PF(pairs[0][0], prime)
PF(pairs[0][1], prime)
for (a, b) in pairs[1:]:
	tmp = set()
	for i in prime:
		if a % i == 0 or b % i == 0:
			tmp.add(i)
	prime = prime.intersection(tmp)
if len(prime) > 0:
	print(int(prime.pop()))
else:
	print(-1)


import functools
import time
from collections import Counter

def timer(func):

	@functools.wraps(func)
	def wrapper(*args, **kwargs):
		stime = time.perf_counter()
		res = func(*args, **kwargs)
		elapsed = time.perf_counter() - stime
		print(f'{func.__name__} in {elapsed:.4f} secs')
		return res
	return wrapper

class solver:

	def __init__(self):
		pass

	def __call__(self):

		def get(a):
			ans = set()
			x = 2
			while x * x <= a:
				if a % x == 0:
					ans.add(x)
					while a % x == 0:
						a = a // x
				x += 1
			if a > 1:
				ans.add(a)
			return ans
		n = int(input())
		ab = list()
		for _ in range(n):
			ab.append(tuple(map(int, input().strip().split())))
		s = set()
		s.update(get(ab[0][0]))
		s.update(get(ab[0][1]))
		for x in s:
			ok = True
			for (a, b) in ab:
				if a % x != 0 and b % x != 0:
					ok = False
					break
			if ok:
				print(x)
				exit(0)
		print('-1')
solver()()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
import math
from collections import Counter
from bisect import bisect_right
import heapq

def prime_factors(x):
	s = set()
	n = x
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			s.add(i)
		i += 1
	if n > 1:
		s.add(n)
	return s

def check(ele):
	for item in ls:
		if item[0] % ele != 0 and item[1] % ele != 0:
			return False
	return True
n = int(input())
f = 0
ans = set()
ls = []
g = 0
import math
for i in range(n):
	(a, b) = map(int, input().split())
	ls.append((a, b))
	g = math.gcd(g, a * b)
for ele in ls:
	if math.gcd(ele[0], g) > 1:
		g = math.gcd(ele[0], g)
	else:
		g = math.gcd(ele[1], g)
print(g if g > 1 else -1)


import sys
input = sys.stdin.readline

def f(a):
	s = []
	n = a
	for i in range(2, int(n ** 0.5) + 1):
		if a % i == 0:
			while a % i == 0:
				a //= i
			s.append(i)
		i += 1
	if a > 1:
		s.append(a)
	return s

def check(elem):
	for item in a:
		if item[0] % elem != 0 and item[1] % elem != 0:
			return False
	return True
n = int(input())
a = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append((x, y))
s = f(a[0][0]) + f(a[0][1])
for elem in s:
	if check(elem):
		print(elem)
		exit()
print(-1)


import sys
input = sys.stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())

class WCD:

	def __init__(self):
		self.n = I()
		self.ab = [tuple(R()) for _ in range(self.n)]

	def ok(self, x):
		for (u, v) in self.ab:
			if u % x and v % x:
				return False
		return True

	def factorize(self, num):
		ret = []
		for i in range(2, int(num ** 0.5) + 1):
			if num % i == 0:
				ret.append(i)
				while num % i == 0:
					num //= i
		if num > 1:
			ret.append(num)
		return ret

	def solve(self):
		factors = self.factorize(self.ab[0][0]) + self.factorize(self.ab[0][1])
		for x in factors:
			if self.ok(x):
				print(x)
				exit()
		print(-1)
		exit()
o = WCD()
o.solve()


import math
gcd = 0
n = int(input())
(a, b) = ([0] * n, [0] * n)
for i in range(n):
	(a[i], b[i]) = 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)


import math

def f(n):
	a = set()
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			a.add(i)
		while n % i == 0:
			n //= i
	if n != 1:
		a.add(n)
	return a
n = int(input())
a = set()
for i in range(n):
	(x, y) = map(int, input().split())
	(x, y) = (max(x, y), min(x, y))
	if i == 0:
		b = f(x)
		b2 = f(y)
		b |= b2
		b = list(b)
	a.add((x, y))
a = list(a)
i = 0
j = 0
while i < len(a) and j < len(b):
	if a[i][0] % b[j] == 0:
		i += 1
	elif a[i][1] % b[j] == 0:
		i += 1
	else:
		i = 0
		j += 1
if i >= len(a):
	print(b[j])
else:
	print(-1)


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)


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 sys
import math
from collections import defaultdict
import bisect

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

def ilele():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 1000000000 + 7

def primeFactors(n):
	A = set()
	while n % 2 == 0:
		A.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			A.add(i)
			n = n // i
	if n > 2:
		A.add(n)
	return list(A)
Z = []
for i in range(int(input())):
	(a, b) = ilele()
	Z.append((a, b))
for i in range(len(Z)):
	(a, b) = Z[i]
	if i == 0:
		B = list(set(primeFactors(a) + primeFactors(b)))
	else:
		C = []
		for j in B:
			if a % j == 0 or b % j == 0:
				C.append(j)
		B = C.copy()
	if len(B) == 0:
		break
if len(B) != 0:
	print(B[0])
else:
	print(-1)


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

def prime_factors(n):
	factors = set()
	while n % 2 == 0:
		factors.add(2)
		n = n / 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.add(i)
			n = n / i
	if n > 2:
		factors.add(n)
	return factors
(a, b) = tuple(map(int, input().split()))
factors = prime_factors(a).union(prime_factors(b))
for i in range(n - 1):
	(a, b) = tuple(map(int, input().split()))
	if factors:
		new_factors = set()
		for f in factors:
			if a % f == 0 or b % f == 0:
				new_factors.add(f)
		factors = new_factors
print(int(factors.pop()) if factors else -1)


def prime(a):
	i = 2
	if a <= 1:
		return 0
	if a == 2 or a == 3:
		return 1
	while i * i <= a:
		if a % i == 0:
			return 0
		i += 1
	return 1

def faq(a):
	l = []
	l1 = []
	i = 1
	while i * i <= a:
		if a % i == 0:
			l.append(i)
			l.append(a // i)
		i += 1
	for i in range(0, len(l)):
		if prime(l[i]) == 1:
			l1.append(l[i])
	return l1
n = int(input())
(a, b) = map(int, input().split())
c = a * b
l = faq(a)
l.extend(faq(b))
l = list(set(l))
for i in range(1, n):
	(a, b) = map(int, input().split())
	if a * b != c:
		j = 0
		while j < len(l):
			c = a * b
			if c % l[j] != 0:
				l.remove(l[j])
				if len(l) == 0:
					print(-1)
			else:
				j += 1
if len(l) != 0:
	print(l[0])


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')
	elif 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')


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])


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
n = int(input())
(al, bl) = (list(), list())
last = 0
for i in range(n):
	(a, b) = map(int, input().split())
	al.append(a)
	bl.append(b)
	last = gcd(last, al[i] * bl[i])
for i in range(n):
	if gcd(last, al[i]) > 1:
		last = gcd(last, al[i])
	else:
		last = gcd(last, bl[i])
if last == 1:
	print(-1)
else:
	print(last)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict
import math

def getFactors(n):
	prime = defaultdict(int)
	while n % 2 == 0:
		prime[2] += 1
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			prime[i] += 1
			n = n // i
	if n > 2:
		prime[n] += 1
	return prime
n = int(input())
(first, second) = map(int, input().split())
first_pf = getFactors(first)
second_pf = getFactors(second)
lines = []
for i in range(n - 1):
	lines.append(tuple(map(int, input().split())))
ans = -1
found = False
for factor in first_pf:
	this_good = True
	for line in lines:
		if line[0] % factor and line[1] % factor:
			this_good = False
			break
	if this_good:
		ans = factor
		found = True
		break
if not found:
	for factor in second_pf:
		this_good = True
		for line in lines:
			if line[0] % factor and line[1] % factor:
				this_good = False
				break
		if this_good:
			ans = factor
			break
print(ans)


n = int(input())
(a, b) = ([0] * n, [0] * n)
g = 0

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


import sys

def prime_factors(a):
	factors = set()
	i = 2
	orig = a
	while i <= int(orig ** 0.5) + 1:
		while a % i == 0:
			a = a // i
			factors.add(i)
		i += 1
	if a > 1:
		factors.add(a)
	return factors
N = int(sys.stdin.readline())
(a, b) = [int(x) for x in sys.stdin.readline().split()]
divisors = prime_factors(a).union(prime_factors(b))
divisors = [int(x) for x in divisors]
for i in range(N - 1):
	checker = []
	(c, d) = [int(x) for x in sys.stdin.readline().split()]
	if divisors:
		for i in divisors:
			if c * d % i == 0:
				checker.append(i)
	divisors = checker
print(divisors[0] if divisors != [] else '-1')


def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
nums = [list(map(int, input().split())) for _ in range(int(input()))]
prods = [x * y for (x, y) in nums]
divisors = []
divisors += prime_factors(nums[0][0])
divisors += prime_factors(nums[0][1])
prods = list(dict.fromkeys(prods))
numWorks = 0
i = -1
while numWorks < len(prods) and i < len(divisors) - 1:
	i += 1
	numWorks = 0
	for j in range(0, len(prods)):
		if prods[j] % divisors[i] == 0:
			numWorks += 1
		else:
			break
if numWorks == len(prods):
	print(divisors[i])
else:
	print(-1)


import sys
import math
from collections import defaultdict, deque
import _operator
input = sys.stdin.readline

def inar():
	return [int(el) for el in input().split()]

def main():
	n = int(input())
	pairs = []
	for i in range(n):
		(x, y) = inar()
		pairs.append([x, y])
	counter = 0
	take = []
	for i in range(2, int(pairs[0][0] ** 0.5) + 1):
		if pairs[0][0] % i == 0:
			take.append(i)
			while pairs[0][0] % i == 0:
				pairs[0][0] //= i
	if pairs[0][0] > 1:
		take.append(pairs[0][0])
	ans = -1
	for j in range(len(take)):
		counter = 0
		for i in range(1, n):
			if pairs[i][0] % take[j] == 0 or pairs[i][1] % take[j] == 0:
				continue
			else:
				counter = 1
				break
		if counter == 0:
			ans = take[j]
			break
	if ans != -1:
		print(ans)
	else:
		counter = 0
		take = []
		for i in range(2, int(pairs[0][1] ** 0.5) + 1):
			if pairs[0][1] % i == 0:
				take.append(i)
				while pairs[0][1] % i == 0:
					pairs[0][1] //= i
		if pairs[0][1] > 1:
			take.append(pairs[0][1])
		ans = -1
		for j in range(len(take)):
			counter = 0
			for i in range(1, n):
				if pairs[i][0] % take[j] == 0 or pairs[i][1] % take[j] == 0:
					continue
				else:
					counter = 1
					break
			if counter == 0:
				ans = take[j]
				break
		print(ans)
main()


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))


import sys
import os
import io
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
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(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def li():
	return list(map(int, input().split()))
t = 1
for _ in range(t):
	n = ii()
	d = defaultdict(lambda : 0)
	l = []
	for i in range(n):
		(a, b) = li()
		l.append([a, b])
	x = list(set(primeFactors(a) + primeFactors(b)))
	ff = 0
	for i in x:
		f = 0
		for j in range(n):
			if l[j][0] % i != 0 and l[j][1] % i != 0:
				f = 1
				break
		if f == 0:
			print(int(i))
			ff = 1
			break
	if ff == 0:
		print(-1)


from math import gcd
n = int(input())
a = [tuple(map(int, input().split())) for i in range(n)]
ans = 0
for (x, y) in a:
	ans = gcd(x * y, ans)
for (x, y) in a:
	if gcd(ans, x) > 1:
		ans = gcd(ans, x)
	else:
		ans = gcd(ans, y)
print(-1 if ans == 1 else ans)


import math

def factors(a, l):
	for i in range(2, int(a ** 0.5) + 1):
		if a % i == 0:
			l.append(i)
			while a % i == 0:
				a = a // i
	if a > 1:
		l.append(a)
n = int(input())
l = []
k = []
for i in range(n):
	(x, y) = map(int, input().split())
	if i == 0:
		factors(x, l)
		factors(y, l)
	k.append([x, y])
l = list(set(l))
for i in l:
	c = 0
	for j in k:
		if j[0] % i and j[1] % i:
			c = 1
			break
	if c == 0:
		print(i)
		break
else:
	print(-1)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

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

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		n = ri()
		z = []
		for i in range(n):
			(a, b) = ria()
			z.append([a, b])
		shortlistedanswers = primeFactors(z[0][0]) + primeFactors(z[0][1])
		shortlistedanswers = list(set(shortlistedanswers))
		c = 0
		for i in shortlistedanswers:
			c = 0
			for j in z:
				if j[0] % i != 0 and j[1] % i != 0:
					c = 1
					break
			if c == 0:
				wi(i)
				break
		if c == 1:
			wi(-1)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


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()]
(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()]
	s = []
	for p in d:
		if a % p != 0 and b % p != 0:
			s.append(p)
	for ele in s:
		d.remove(ele)
	if len(d) == 0:
		f = 1
		ans = -1
		break
if f != 1:
	ans = d[0]
print(ans)


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def primeFactors(n):
	while n % 2 == 0:
		return 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			return i
	if n > 2:
		return n
	return -1

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
dd = []
d = defaultdict(lambda : 0)
temp = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	dd.append([a, b])
	a = a * b
	temp = gcd(a, temp)
for i in range(n):
	if math.gcd(temp, dd[i][1]) != 1:
		temp = math.gcd(dd[i][1], temp)
	elif math.gcd(temp, dd[i][0]) != 1:
		temp = math.gcd(dd[i][0], temp)
	else:
		print(-1)
		exit()
print(primeFactors(temp))


n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
	(a[i], b[i]) = map(int, input().split())
d = []
for x in (a[0], b[0]):
	for i in range(2, x + 1):
		if i * i > x:
			break
		if x % i == 0:
			d.append(i)
			while x % i == 0:
				x //= i
	if x != 1:
		d.append(x)
for x in set(d):
	ok = True
	for i in range(1, n):
		if a[i] % x != 0 and b[i] % x != 0:
			ok = False
			break
	if ok:
		print(x)
		exit(0)
print(-1)


def f(a):
	s = set()
	n = a
	i = 2
	while i ** 2 <= a:
		if a % i == 0:
			while a % i == 0:
				a //= i
			s.add(i)
		i += 1
	if a > 1:
		s.add(a)
	return s

def check(elem):
	for item in a:
		if item[0] % elem != 0 and item[1] % elem != 0:
			return False
	return True
n = int(input())
a = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append((x, y))
s = f(a[0][0]).union(f(a[0][1]))
for elem in s:
	if check(elem):
		print(elem)
		exit()
print(-1)


import math
N = int(input())
List = []
maxval = 0
for i in range(N):
	(u, v) = map(int, input().split())
	List.append([u, v])
	maxval = math.gcd(maxval, u * v)
for i in List:
	if math.gcd(i[0], maxval) > 1:
		maxval = math.gcd(i[0], maxval)
	else:
		maxval = math.gcd(i[1], maxval)
if maxval == 1:
	print(-1)
else:
	print(maxval)


import math
n = int(input())

def primeFactor(n):
	fac = []
	count = 0
	while n % 2 == 0:
		count += 1
		n = n // 2
	if count != 0:
		fac += [(2, count)]
	top = math.floor(math.sqrt(n))
	i = 3
	count = 0
	while i <= top:
		if n % i == 0:
			count += 1
			n = n // i
		else:
			if count != 0:
				fac += [(i, count)]
				count = 0
			i += 2
	if n > 2:
		fac += [(n, 1)]
	return fac

def divisors(n):
	divisors = []
	fac = primeFactor(n)
	length = len(fac)
	for pair in fac:
		num = len(divisors)
		for i in range(pair[1]):
			mult = pair[0] ** (i + 1)
			for i in range(num):
				divisors += [divisors[i] * mult]
			divisors += [mult]
	return divisors

def getFactors(n):
	pairs = primeFactor(n)
	return [pair[0] for pair in pairs]
temp = []
for i in range(n):
	(left, right) = map(int, input().split(' '))
	if i == 0:
		divs = list(set(getFactors(left) + getFactors(right)))
	else:
		temp = []
		for i in divs:
			if left % i == 0 or right % i == 0:
				temp += [i]
		divs = temp
	if divs == []:
		print(-1)
		exit()
print(divs[0])


import math
n = int(input())
ls = []
for _ in range(n):
	ls.append(tuple(map(int, input().split())))
ans = 0
for (x, y) in ls:
	ans = math.gcd(x * y, ans)
for (x, y) in ls:
	if math.gcd(ans, x) > 1:
		ans = math.gcd(ans, x)
	else:
		ans = math.gcd(ans, y)
print(-1 if ans == 1 else ans)


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 sys
input = sys.stdin.readline

def primes(n):
	fact = []
	if n % 2 == 0:
		fact.extend([2])
		while n % 2 == 0:
			n //= 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			fact.append(i)
			while n % i == 0:
				n //= i
	if n != 1:
		fact.append(n)
	return fact

def prog():
	n = int(input())
	a = [list(map(int, input().split())) for i in range(n)]
	valid_primes = set(primes(a[0][0]) + primes(a[0][1]))
	for i in range(1, n):
		to_remove = []
		for p in valid_primes:
			if a[i][0] % p != 0 and a[i][1] % p != 0:
				to_remove.append(p)
		for p in to_remove:
			valid_primes.remove(p)
	if valid_primes:
		print(list(valid_primes)[0])
	else:
		print(-1)
prog()


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
sum = 0
(l, r) = (0, 0)
while n > 0:
	(l, r) = input().split()
	l = int(l)
	r = int(r)
	t = gcd(l, r)
	t = int(l * r) // t
	sum = gcd(sum, t)
	n -= 1
if sum == 1:
	print(-1)
elif gcd(l, sum) == 1:
	i = 2
	sum = gcd(r, sum)
	while sum >= i * i:
		if sum % i == 0:
			sum = i
			break
		i += 1
	print(int(sum))
else:
	i = 2
	sum = gcd(l, sum)
	while sum >= i * i:
		if sum % i == 0:
			sum = i
			break
		i += 1
	print(int(sum))


import math
n = int(input())
(a, b) = map(int, input().split())
pms = [a, b]
for i in range(2, math.ceil(math.sqrt(a)) + 1):
	cur = 0
	if i != a and a % i == 0:
		pms.append(i)
		while a % i == 0:
			a = a // i
if a > 1:
	pms.append(a)
for i in range(2, math.ceil(math.sqrt(b)) + 1):
	if i != b and b % i == 0:
		pms.append(i)
		while b % i == 0:
			b = b // i
if b > 1:
	pms.append(b)
pms = list(set(pms))
pms1 = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	for j in pms:
		if a % j == 0 or b % j == 0:
			pms1.append(j)
	pms = pms1
	if len(pms) == 0:
		break
	pms1 = []
if len(pms):
	print(pms[0])
else:
	print(-1)


q = int(input())
(a, b) = map(int, input().split())
s = set()
for x in [a, b]:
	if x % 2 == 0:
		s.add(2)
		while x % 2 == 0:
			x //= 2
	i = 3
	while i * i <= x:
		if x % i == 0:
			s.add(i)
			while x % i == 0:
				x //= i
		i += 2
	if x != 1:
		s.add(x)
for k in range(q - 1):
	(u, v) = map(int, input().split())
	s0 = set()
	for z in s:
		if u % z == 0 or v % z == 0:
			s0.add(z)
	s = s0
if len(s) == 0:
	print(-1)
else:
	print(min(s))


def fact(n):
	i = 2
	arr = set()
	while i * i <= n:
		if n % i == 0:
			arr.add(i)
			while n % i == 0:
				n //= i
		i += 1
	if n > 1:
		arr.add(n)
	return list(arr)
arr = []
for i in range(int(input())):
	(a, b) = map(int, input().split())
	arr.append([a, b])
(a, b) = arr[0]
prime_dvsrs = list(set(fact(a) + fact(b)))
for i in prime_dvsrs:
	flag = 0
	for j in range(1, len(arr)):
		(x, y) = arr[j]
		if x % i != 0 and y % i != 0:
			flag = 1
			break
	if flag == 0:
		print(i)
		break
else:
	print(-1)


(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):
	global a
	for i in a:
		if i[0] % x > 0 and i[1] % x > 0:
			return False
	return True

def judge(x):
	global 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]):
	exit(0)
if judge(a[0][1]):
	exit(0)
print(-1)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
a = []
b = []
for i in range(n):
	(A, B) = map(int, input().split())
	a.append(A)
	b.append(B)
ans = -1
x = 0
for i in range(n):
	x = gcd(x, a[i] * b[i])
if x != 1:
	for i in range(n):
		if gcd(x, a[i]) > 1:
			x = gcd(x, a[i])
			ans = gcd(x, a[i])
		else:
			x = gcd(x, b[i])
			ans = gcd(x, b[i])
print(ans)


from sys import stdin
input = stdin.readline
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
mp = lambda : map(int, input().split())
it = lambda : int(input())
ls = lambda : list(input().strip())
mt = lambda r: [list(mp()) for _ in range(r)]
mod = 1000000007

def isprime(n):
	for j in range(3, int(sqrt(n)) + 1, 2):
		if n % j == 0:
			return 0
	return 1

def factors(n):
	s = set()
	s.add(n)
	for j in range(2, int(sqrt(n)) + 1):
		if n % j == 0:
			s.add(j)
			s.add(n // j)
	return s

def pfactors(n):
	pm = set()
	flg = 0
	while n % 2 == 0:
		flg = 1
		n //= 2
	if flg:
		pm.add(2)
	for cc in range(3, int(sqrt(n)) + 1, 2):
		if n % cc == 0:
			pm.add(cc)
			while n % cc == 0:
				n //= cc
	if n > 1:
		pm.add(n)
	return pm
k = mt(it())
fc = pfactors(k[0][0])
fc.update(pfactors(k[0][1]))
out = -1
for ele in fc:
	ans = ele
	for (fs, scd) in list(k):
		if fs % ele and scd % ele:
			ans = 0
			break
	if ans:
		out = ans
		break
print(out)


def countdiv(n):
	count = set()
	i = 2
	nn = n
	while n > 1:
		if n % i == 0:
			count.add(i)
			n //= i
		else:
			i += 1
		if i > nn ** 0.5 + 1:
			count.add(n)
			break
	return count

def countt(n, s):
	ss = set()
	for i in s:
		if n % i == 0:
			ss.add(i)
	return ss
n = int(input())
a = list(map(int, input().split()))
s = countdiv(a[0]).union(countdiv(a[1]))
for itr in range(1, n):
	a = list(map(int, input().split()))
	s = countt(a[0] * a[1], s)
	if len(s) == 0:
		break
if len(s) == 0:
	print(-1)
else:
	print(list(s)[0])


from sys import stdin, stdout
import bisect
import math
from collections import deque
mod = 10 ** 9 + 7

def st():
	return list(stdin.readline().strip())

def inp():
	return int(stdin.readline())

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

def mp():
	return map(int, stdin.readline().split())

def pr(n):
	stdout.write(str(n) + '\n')

def DFS(dictionary, vertex, visited):
	visited[vertex] = True
	stack = [vertex]
	print(vertex)
	while stack:
		a = stack.pop()
		for i in dictionary[a]:
			if not visited[i]:
				print(i)
				visited[i] = True
				stack.append(i)

def BFS(d, visited, i, value, dis):
	value[i] = dis
	visited[i] = True
	q = deque()
	q.append(i)
	while q:
		a = q.popleft()
		for i in d[a]:
			if not visited[i]:
				visited[i] = True
				value[i] = value[a] + 1
				q.append(i)

def soe(limit):
	l = [1] * (limit + 1)
	l[0] = 0
	l[1] = 0
	prime = []
	for i in range(2, limit + 1):
		if l[i]:
			for j in range(i * i, limit + 1, i):
				l[j] = 0
	for i in range(2, limit + 1):
		if l[i]:
			prime.append(i)
	return prime

def segsoe(low, high):
	limit = int(high ** 0.5) + 1
	prime = soe(limit)
	n = high - low + 1
	l = [0] * (n + 1)
	for i in range(len(prime)):
		lowlimit = low // prime[i] * prime[i]
		if lowlimit < low:
			lowlimit += prime[i]
		if lowlimit == prime[i]:
			lowlimit += prime[i]
		for j in range(lowlimit, high + 1, prime[i]):
			l[j - low] = 1
	for i in range(low, high + 1):
		if not l[i - low]:
			if i != 1:
				print(i)

def gcd(a, b):
	while b:
		a = a % b
		(b, a) = (a, b)
	return a

def power(a, n):
	r = 1
	while n:
		if n & 1:
			r = r * a
		a *= a
		n = n >> 1
	return r

def prime(n, l):
	i = 2
	while i * i <= n:
		if n % i == 0:
			l.append(i)
			while n % i == 0:
				n //= i
		i += 1
	if n > 1:
		l.append(n)

def solve():
	n = inp()
	l = []
	x = []
	for _ in range(n):
		(a, b) = mp()
		if _ == 0:
			prime(a, l)
			prime(b, l)
		x.append([a, b])
	l = list(set(l))
	for i in l:
		c = 0
		for j in range(1, len(x)):
			a = x[j][0]
			b = x[j][1]
			if a % i != 0 and b % i != 0:
				c = 1
				break
		if c == 0:
			pr(i)
			return
	pr(-1)
for _ in range(1):
	solve()


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
from collections import defaultdict
from math import sqrt
INF = pow(2, 63)

def isPrime(number):
	assert isinstance(number, int) and number >= 0, "'number' must been an int and positive"
	status = True
	if number <= 1:
		status = False
	for divisor in range(2, int(round(sqrt(number))) + 1):
		if number % divisor == 0:
			status = False
			break
	assert isinstance(status, bool), "'status' must been from type bool"
	return status
import math

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

def greatest_common_divisor(a: int, b: int) -> int:
	return abs(b) if a == 0 else greatest_common_divisor(b % a, a)

def solveb(n, tuparr):
	pset = set(primeFactors(tuparr[0][0])) | set(primeFactors(tuparr[0][1]))
	for p in pset:
		cnt = 0
		for (i, tup) in enumerate(tuparr):
			if greatest_common_divisor(tup[0], p) == 1 and greatest_common_divisor(tup[1], p) == 1:
				break
			else:
				cnt += 1
		if cnt == n:
			return p
	return -1

def solve(n, arr):
	m = defaultdict(int)
	for c in arr:
		m[c] += 1
	if max(m.values()) <= 1 and n != 1:
		print('No')
	else:
		print('Yes')

@bootstrap
def rec(i, k, arr, mp, f=0):
	pass

def main():
	n = int(input().strip())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().strip().split())))
	print(solveb(n, arr))
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


def d(x):
	for dl in range(2, int(x ** 0.5) + 1):
		if x % dl == 0:
			return dl
	return x

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
n = int(input())
(a, b) = map(int, input().split())
for i in range(n - 1):
	(an, bn) = map(int, input().split())
	(a, b) = (gcd(an * bn, a), gcd(an * bn, b))
if a > 1:
	print(d(a))
elif b > 1:
	print(d(b))
else:
	print(-1)


import math

def primeFactors(number):
	primeFactors = set()
	while number % 2 == 0:
		primeFactors.add(2)
		number = number / 2
	for i in range(3, int(math.sqrt(number)) + 1, 2):
		while number % i == 0:
			primeFactors.add(i)
			number = number / i
	if number > 2:
		primeFactors.add(int(number))
	return primeFactors

def wcd(list_of_pair):
	boolean = False
	count = 0
	list_of_pair = sorted(list_of_pair)
	(a, b) = list_of_pair[0]
	ans = primeFactors(a).union(primeFactors(b))
	for s in list_of_pair:
		(a, b) = s
		for j in list(ans):
			if a % j != 0 and b % j != 0:
				ans.remove(j)
	if ans:
		return ans.pop()
	else:
		return -1
q = int(input())
list_of_pairs = [-1] * q
for q_itr in range(q):
	(a, b) = map(int, input().rstrip().split())
	list_of_pairs[q_itr] = [(a, b), (b, a)][a > b]
result = wcd(list_of_pairs)
print(result)


import math

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
(a, b) = map(int, input().split())
for i in range(n - 1):
	(x, y) = map(int, input().split())
	x = x * y
	a = gcd(a, x)
	b = gcd(b, x)
if a == 1 and b == 1:
	print(-1)
	exit()
else:
	i = 2
	while i * i <= a or i * i <= b:
		if a % i == 0:
			a = i
			break
		if b % i == 0:
			b = i
			break
		i += 1
if a == 1:
	print(b)
else:
	print(a)


import sys

def trial_division(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n = n // 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n = n // f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a
n = int(sys.stdin.readline())
a = []
for i in range(n):
	(b, c) = map(int, sys.stdin.readline().split())
	a.append((b, c))
ans = 0
if n == 1:
	ans = a[0][0]
else:
	arr = trial_division(a[0][0])
	arr.extend(trial_division(a[0][1]))
	divs = set(arr)
	for i in range(1, n):
		to_remove = set()
		for d in divs:
			if a[i][0] % d != 0 and a[i][1] % d != 0:
				to_remove.add(d)
		for r in to_remove:
			divs.remove(r)
	if len(divs) > 0:
		ans = divs.pop()
	else:
		ans = -1
print(ans)


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 gcd
n = int(input())
g = 1
a = [0] * n
b = [0] * n
for i in range(1):
	(a[i], b[i]) = map(int, input().split())
	g = a[i] * b[i]
for i in range(1, n):
	(a[i], b[i]) = map(int, input().split())
	g = gcd(a[i] * b[i], g)
for i in range(n):
	if gcd(a[i], g) > 1:
		g = gcd(a[i], g)
	elif gcd(b[i], g) > 1:
		g = gcd(b[i], g)
	else:
		print(-1)
		exit()
print(g)


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)
		exit()
print(primes.pop())


import math
facArr = set()
ind = 0

def primeFactors(n):
	global facArr
	while n % 2 == 0:
		facArr.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			facArr.add(i)
			n = n // i
	if n > 2:
		facArr.add(n)
n = int(input())
a = []
b = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append(x)
	b.append(y)
primeFactors(a[0])
primeFactors(b[0])
factors = sorted(list(facArr))
for factor in factors:
	for i in range(1, n):
		if a[i] % factor != 0 and b[i] % factor != 0:
			break
	else:
		print(factor)
		break
else:
	print(-1)


def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
n = int(input())
Ar = [[None, None] for _ in range(n)]
for i in range(n):
	(Ar[i][0], Ar[i][1]) = map(int, input().split())
A = prime_factors(Ar[0][0])
for x in prime_factors(Ar[0][1]):
	A.append(x)
A = list(set(A))
cnt = 0
for j in A:
	for i in range(n):
		if Ar[i][0] % j == 0 or Ar[i][1] % j == 0:
			cnt += 1
		if cnt != i + 1:
			cnt = 0
			break
	if cnt == n:
		print(j)
		break
if cnt == 0:
	print(-1)


from sys import stdin, stdout
import math
n = int(stdin.readline())
pairs = [tuple(map(int, line.split())) for line in stdin]

def getFactors(n):
	factors = set()
	while n % 2 == 0:
		factors.add(2)
		n = n // 2
	k = 3
	while k <= math.sqrt(n):
		if n % k == 0:
			n = n // k
			factors.add(k)
		else:
			k += 2
	if n > 1:
		factors.add(n)
	return factors
tab = {}
(a, b) = pairs[0]
tab[a] = getFactors(a)
tab[b] = getFactors(b)
common = tab[a] | tab[b]
for factor in common:
	is_div = True
	for (a, b) in pairs:
		if a % factor == 0 or b % factor == 0:
			continue
		else:
			is_div = False
			break
	if is_div:
		print(factor)
		exit()
print(-1)


def prime_divs(n):
	res = set()
	d = 2
	while d * d <= n:
		if n % d == 0:
			while n % d == 0:
				n = n // d
			res.add(d)
		else:
			d = d + 1
	if n > 1:
		res.add(n)
	return res
n = int(input())
ls = []
for i in range(n):
	(a, b) = list(map(int, input().split()))
	ls.append([a, b])
set1 = prime_divs(ls[0][0])
set1 = set1.union(prime_divs(ls[0][1]))
for i in range(1, n):
	to_remove = set()
	for d in set1:
		if not (ls[i][0] % d == 0 or ls[i][1] % d == 0):
			to_remove.add(d)
	set1 = set1.difference(to_remove)
if len(set1) == 0:
	print(-1)
else:
	print(list(set1)[0])


def prime_factorize(n):
	primes_factors = {}
	while n % 2 == 0:
		n >>= 1
		primes_factors[2] = primes_factors.get(2, 0) + 1
	for i in range(3, int(n ** (1 / 2)) + 1, 2):
		while n % i == 0:
			n //= i
			primes_factors[i] = primes_factors.get(i, 0) + 1
	if n > 1:
		primes_factors[n] = 1
	return [*primes_factors.keys()]
n = int(input())
a = set([])
for _ in range(n):
	(i, j) = map(int, input().split())
	if _ == 0:
		a = set(prime_factorize(i) + prime_factorize(j))
		continue
	for k in [*a]:
		if i % k and j % k:
			a.remove(k)
print([*a][0] if len(a) else -1)


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

def pr(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			a.append(i)
			n = n / i
	if n > 2:
		a.append(n)
	return list(set(a))
n = int(input())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
if n == 1:
	print(a[0][0])
else:
	b = []
	b.append(pr(a[0][0]))
	b.append(pr(a[0][1]))
	c = set([])
	for i in range(len(b)):
		for j in range(len(b[i])):
			c.add(b[i][j])
	c = list(c)
	e = 0
	for i in range(len(c)):
		b = 0
		for j in range(n):
			if a[j][0] % c[i] == 0 or a[j][1] % c[i] == 0:
				b += 1
		if b == n:
			e = 1
			print(int(c[i]))
			break
	if e == 0:
		print(-1)


def get_prime(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime
prime = get_prime(10 ** 6)

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res
import sys
from math import gcd
input = sys.stdin.buffer.readline
n = int(input())
(A, B) = map(int, input().split())
now = A * B
for i in range(n - 1):
	(a, b) = map(int, input().split())
	now = gcd(now, a * b)
if now > 1:
	p1 = factorization(A)
	p2 = factorization(B)
	P = p1 + p2
	for p in P:
		if now % p == 0:
			print(p)
			break
else:
	print(-1)


from math import gcd
n = int(input())
(a, b) = [int(x) for x in input().split()]
for i in range(1, n):
	(x, y) = [int(x) for x in input().split()]
	xy = x * y
	if a > 1:
		a = gcd(a, xy)
	if b > 1:
		b = gcd(b, xy)
g = max(a, b)
if g == 1:
	print(-1)
else:
	i = 2
	while i * i <= g:
		if g % i == 0:
			print(i)
			break
		i += 1
	else:
		print(g)