Chef has a sequence of positive integers $A_1, A_2, \ldots, A_N$. He wants to split this sequence into two non-empty (not necessarily contiguous) subsequences $B$ and $C$ such that $\mathrm{GCD}\,(B) + \mathrm{GCD}\,(C)$ is maximum possible. Help him find this maximum value.
Note: The greatest common divisor (GCD) of a sequence of positive integers is the largest positive integer that divides each element of this sequence. For example, the GCD of the sequence $(8, 12)$ is $4$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the maximum value of $\mathrm{GCD}\,(B) + \mathrm{GCD}\,(C)$.

-----Constraints-----
- $1 \le T \le 10$
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (20 points): $2 \le N \le 20$
Subtask #2 (80 points): original constraints

-----Example Input-----
1              
4                    
4 4 7 6                    

-----Example Output-----
9

-----Explanation-----
Example case 1: For example, the sequence $A$ can be divided into subsequences $B = (4, 4, 6)$ and $C = (7)$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import sys

def read_line():
	return sys.stdin.readline().split()

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

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def gcd(x, y):
	while x != 0 and y != 0:
		z = y
		y = x % y
		x = z
	return x + y

def compute_other_gcd(A, gcd1):
	ret = 0
	for x in A:
		if x % gcd1 != 0:
			ret = gcd(ret, x)
	if ret == 0:
		return A[-1]
	return ret
T = read_int()
for _test in range(T):
	N = read_int()
	A = read_int_line()
	A.sort()
	d = 1
	answer = 0
	while d * d <= A[0]:
		if A[0] % d == 0:
			answer = max(answer, d + compute_other_gcd(A, d))
			answer = max(answer, A[0] // d + compute_other_gcd(A, A[0] // d))
		d += 1
	print(answer)


import math
T = int(input())
for j in range(T):
	n = int(input())
	A = list(set(map(int, input().split())))
	A.sort()
	n_1 = len(A)
	if n_1 == 1:
		print(2 * A[0])
	elif n_1 == 2:
		print(A[0] + A[1])
	else:
		gcd_a = A[-1]
		gcd_b = A[-2]
		gcd_c = 0
		for i in range(0, n_1 - 2):
			gcd_c = math.gcd(gcd_c, A[i])
		op1 = gcd_a + math.gcd(gcd_c, gcd_b)
		op2 = gcd_b + math.gcd(gcd_c, gcd_a)
		print(max(op1, op2))


import math
testcase = int(input())
for i in range(testcase):
	n = int(input())
	l = [int(i) for i in input().split()]
	l = sorted(list(set(l)))
	if len(l) == 1:
		print(2 * l[0])
	elif len(l) == 2:
		print(l[0] + l[1])
	else:
		res = l[0]
		for i in range(0, len(l) - 2):
			res = math.gcd(res, l[i])
		a = math.gcd(res, l[-1]) + l[-2]
		b = math.gcd(res, l[-2]) + l[-1]
		print(max(a, b))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for i in range(t):
	n = int(input())
	l = list(set(map(int, input().split())))
	n = len(l)
	if n == 1:
		print(l[0] * 2)
		continue
	pregcd = [0] * n
	postgcd = [0] * n
	pregcd[0] = l[0]
	postgcd[-1] = l[-1]
	for i in range(1, n):
		pregcd[i] = gcd(pregcd[i - 1], l[i])
	for i in range(n - 2, -1, -1):
		postgcd[i] = gcd(postgcd[i + 1], l[i])
	ans = l[0] + postgcd[1]
	for i in range(1, n - 1):
		sum1 = l[i] + gcd(pregcd[i - 1], postgcd[i + 1])
		if sum1 > ans:
			ans = sum1
	sum1 = l[n - 1] + pregcd[n - 2]
	if sum1 > ans:
		ans = sum1
	print(ans)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = []
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			b.append(a[i])
	b.append(a[n - 1])
	hcf = b[0]
	l = len(b)
	for i in range(1, l - 1):
		hcf = gcd(hcf, b[i])
		if hcf == 1:
			break
	mx = b[l - 1] + hcf
	b[l - 1] += b[l - 2]
	b[l - 2] = b[l - 1] - b[l - 2]
	b[l - 1] = b[l - 1] - b[l - 2]
	hcf = b[0]
	for i in range(1, l - 1):
		hcf = gcd(hcf, b[i])
		if hcf == 1:
			break
	if mx > b[l - 1] + hcf:
		print(mx)
	else:
		print(b[l - 1] + hcf)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(set(map(int, input().split())))
	if len(a) == 1:
		print(a[0] * 2)
	elif len(a) == 2:
		print(a[0] + a[1])
	else:
		a.sort()
		b = a[-1]
		gcd = math.gcd(a[0], a[1])
		for i in range(2, len(a) - 1):
			gcd = math.gcd(gcd, a[i])
		l1 = b + gcd
		b = a[len(a) - 2]
		a.remove(b)
		gcd = math.gcd(a[0], a[1])
		for i in range(2, len(a) - 1):
			gcd = math.gcd(gcd, a[i])
		l2 = b + gcd
		if l1 > l2:
			print(l1)
		else:
			print(l2)


import math
for i in range(int(input())):
	p = int(input())
	a = list(set(map(int, input().split())))
	a.sort()
	c = len(a)
	if c == 1:
		print(2 * a[0])
	else:
		x = a[0]
		y = a[-1]
		for j in range(c):
			x1 = math.gcd(x, a[j])
			x2 = math.gcd(y, a[j])
			z = math.gcd(x, y)
			o1 = x1 + y
			o2 = x2 + x
			o3 = z + a[j]
			m = max(o1, o2, o3)
			if o1 == m:
				x = x1
			elif o2 == m:
				y = x2
			else:
				x = z
				y = a[j]
		print(x + y)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	newa = list(set(a))
	if len(newa) == 1:
		print(newa[0] * 2)
	elif len(newa) == 2:
		print(sum(newa))
	else:
		newa.sort()
		m1 = newa.pop()
		m2 = newa.pop()
		gcd = newa[0]
		for i in range(1, len(newa)):
			gcd = math.gcd(gcd, newa[i])
			if gcd == 1:
				break
		s1 = math.gcd(gcd, m1)
		s2 = math.gcd(gcd, m2)
		print(max(s1 + m2, s2 + m1))


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l = list(set(l))
	n = len(l)
	if len(l) == 1:
		print(l[0] * 2)
	p = [0 for x in range(n)]
	s = [0 for x in range(n)]
	ans1 = 0
	p[0] = l[0]
	for i in range(1, n):
		p[i] = gcd(l[i], p[i - 1])
	s[n - 1] = l[n - 1]
	for i in range(n - 2, -1, -1):
		s[i] = gcd(l[i], s[i + 1])
	for i in range(n):
		if i == 0:
			ans = s[i + 1] + l[0]
		elif i == n - 1:
			ans = p[n - 2] + l[n - 1]
		else:
			ans = gcd(p[i - 1], s[i + 1]) + l[i]
		ans1 = max(ans1, ans)
	print(ans1)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
for _ in range(int(input())):
	n = int(input())
	a = []
	arr = []
	arr = list(map(int, input().split()))
	arr.sort()
	a.append(arr[0])
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			a.append(arr[i])
	n = len(a)
	g = a[0]
	for i in range(1, n - 2):
		g = gcd(g, a[i])
	if gcd(g, a[n - 1]) + a[n - 2] > gcd(g, a[n - 2]) + a[n - 1]:
		print(gcd(g, a[n - 1]) + a[n - 2])
	else:
		print(gcd(g, a[n - 2]) + a[n - 1])


def gcd(a, b):
	if b == 0:
		return a
	elif a == b:
		return b
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A = list(set(A))
	n = len(A)
	A.sort()
	if len(A) < 2:
		print(A[0] * 2)
	else:
		fgcd = [0 for i in range(n)]
		bgcd = [0 for i in range(n)]
		fgcd[0] = A[0]
		for i in range(1, n):
			fgcd[i] = gcd(fgcd[i - 1], A[i])
		bgcd[-1] = A[-1]
		for i in range(n - 2, -1, -1):
			bgcd[i] = gcd(bgcd[i + 1], A[i])
		temp = bgcd[-1] + fgcd[n - 2]
		for i in range(n - 2, 0, -1):
			if temp < A[i] + gcd(fgcd[i - 1], bgcd[i + 1]):
				temp = A[i] + gcd(fgcd[i - 1], bgcd[i + 1])
		if temp < A[0] + bgcd[1]:
			temp = A[0] + bgcd[1]
		print(temp)


def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(set(map(int, input().split())))
	l.sort(reverse=True)
	n = len(l)
	if len(l) == 1:
		print(2 * l[0])
	else:
		g = l[0]
		h = l[1]
		if n >= 3:
			hc = l[2]
			for j in range(3, n):
				hc = hcf(hc, l[j])
			print(max(hcf(g, hc) + h, g + hcf(h, hc)))
		else:
			print(g + h)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = list(set(a))
	a.sort()
	g = a[0]
	if len(a) == 1:
		print(a[0] + a[0])
		continue
	elif len(a) == 2:
		print(a[0] + a[-1])
		continue
	else:
		for i in range(1, len(a) - 2):
			g = gcd(g, a[i])
		g = max(gcd(g, a[-2]) + a[-1], gcd(g, a[-1]) + a[-2])
	print(g)


import math as m
for _ in range(int(input())):
	length = int(input())
	arr = list(map(int, input().split()))
	if length == 2:
		print(arr[0] + arr[1])
	else:
		tmparr = list(set(arr))
		tmparr.sort()
		fmax = tmparr.pop()
		smax = tmparr.pop()
		p = len(tmparr)
		if p == 0:
			print(fmax + smax)
		else:
			result = tmparr[0]
			for i in range(1, p):
				result = m.gcd(tmparr[i], result)
			gcd0 = result
			gcdH = m.gcd(gcd0, fmax)
			gcdSH = m.gcd(gcd0, smax)
			case11 = fmax + gcdSH
			case22 = smax + gcdH
			print(max(case11, case22))


import math
l = []
t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	x = sorted(list(set(x)))
	if len(x) == 1:
		print(2 * x[0])
	elif len(x) == 2:
		print(sum(x))
	else:
		a = len(x)
		q = x[0]
		for i in range(1, a - 2):
			q = math.gcd(q, x[i])
		c = math.gcd(q, x[-2]) + x[-1]
		d = math.gcd(q, x[-1]) + x[-2]
		print(max(c, d))


import math

def __starting_point():
	for _ in range(int(input())):
		n = int(input())
		a = list(set(map(int, input().split())))
		n = len(a)
		flag = 0
		if n == 1:
			print(a[0] * 2)
		else:
			Lgcd = [0]
			Rgcd = [0]
			for i in range(n):
				gcd = math.gcd(Lgcd[i], a[i])
				Lgcd.append(gcd)
			a = a[::-1]
			for i in range(n):
				gcd = math.gcd(Rgcd[i], a[i])
				Rgcd.append(gcd)
			Rgcd = Rgcd[::-1]
			a = a[::-1]
			ans = []
			for i in range(n):
				gcd = a[i] + math.gcd(Lgcd[i], Rgcd[i + 1])
				ans.append(gcd)
			print(max(ans))
__starting_point()


from math import gcd
__author__ = 'Prateek'

def test():
	n = int(input())
	a = list(map(int, input().split()))
	a = list(set(a))
	n = len(a)
	if len(a) == 1:
		print(2 * a[0])
		return
	g1 = [0 for i in range(n)]
	g2 = [0 for i in range(n)]
	g1[0] = a[0]
	g2[n - 1] = a[n - 1]
	for i in range(1, n):
		g1[i] = gcd(g1[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		g2[i] = gcd(g2[i + 1], a[i])
	ans = 0
	for i in range(n):
		if i == 0:
			ans = max(ans, g2[i + 1] + a[i])
		elif i == n - 1:
			ans = max(ans, g1[i - 1] + a[i])
		else:
			ans = max(ans, gcd(g1[i - 1], g2[i + 1]) + a[i])
	print(ans)
if __author__ == 'Prateek':
	t = int(input())
	for _ in range(t):
		test()


from math import gcd

def gh(a, b):
	if len(a) and len(b):
		x = a[0]
		y = b[0]
		for i in a[1:]:
			x = gcd(x, i)
		for i in b[1:]:
			y = gcd(y, i)
		return x + y
	return 0

def abc(l):
	s = 2 ** len(l)
	i = 0
	d = '{0:0' + str(len(l)) + 'b}'
	ans = 0
	while i < s:
		x = d.format(i)
		a = []
		b = []
		for j in range(len(l)):
			if x[j] == '1':
				a.append(l[j])
			else:
				b.append(l[j])
		ans = max(ans, gh(a, b))
		i += 1
	return ans
import random
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		try:
			d[i] += 1
		except:
			d[i] = 1
	x = list(d.keys())
	x.sort()
	if len(x) == 1:
		print(2 * l[0])
	else:
		ans = x[-1]
		c = x[0]
		for i in range(len(x) - 1):
			c = gcd(c, x[i])
		vy = ans + c
		ans = x[-2]
		c = 0
		for i in range(len(x) - 2):
			c = gcd(c, x[i])
		c = gcd(c, x[-1])
		vx = ans + c
		print(max(vx, vy))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr = list(dict.fromkeys(arr))
	arr.sort(reverse=True)
	if len(arr) == 1:
		ans = 2 * arr[0]
		print(ans)
		continue
	n = len(arr)
	b = arr[0]
	c = arr[1]
	if n >= 3:
		temp = arr[2]
		for i in range(2, n):
			temp = math.gcd(temp, arr[i])
		bval = math.gcd(b, temp)
		cval = math.gcd(c, temp)
		ans = max(bval + c, b + cval)
	else:
		ans = b + c
	print(ans)


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
t = int(input())
for i in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	if len(nums) == 2:
		print(nums[0] + nums[1])
		continue
	sec = [nums[0]]
	pt = 0
	for j in nums:
		if j != sec[pt]:
			sec.append(j)
			pt += 1
	if len(sec) == 2:
		print(sum(sec))
		continue
	elif len(sec) == 1:
		print(sec[0] * 2)
		continue
	final = sec[-1]
	initial = sec[0]
	for a in range(1, len(sec) - 1):
		q = gcd(initial, sec[a])
		initial = q
	final += q
	if sec[0] == 1:
		print(final)
		continue
	start = 0
	end = len(sec) - 1
	while start < end:
		if sec[end] % sec[start] == 0:
			end -= 1
		else:
			start += 1
	fin2 = sec[end]
	initial = sec[0]
	if initial == fin2:
		initial = sec[1]
	for b in range(0, len(sec)):
		if sec[b] != fin2:
			q = gcd(initial, sec[b])
			initial = q
	fin2 += q
	ini = sec[0]
	for qw in range(1, len(sec) - 2):
		ini = gcd(ini, sec[qw])
	g1 = gcd(ini, sec[-2]) + sec[-1]
	g2 = gcd(ini, sec[-1]) + sec[-2]
	print(max(g1, g2, fin2, final))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(set([int(i) for i in input().split()]))
	a.sort()
	max_gcd = []
	if len(a) == 1:
		print(2 * a[0])
	elif len(a) == 2:
		print(a[0] + a[1])
	else:
		f = b = a[-1]
		s = c = a[-2]
		for i in range(0, len(a) - 2):
			b = math.gcd(b, a[i])
			c = math.gcd(c, a[i])
		print(max(b + s, f + c))


def gc(a, b):
	if b == 0:
		return a
	return gc(b, a % b)
for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	b = list(set(b))
	b.sort()
	if len(b) == 1:
		print(2 * b[0])
	elif len(b) == 2:
		print(b[0] + b[1])
	else:
		m = b[-1]
		s = b[-2]
		g = 0
		for j in range(0, len(b) - 2):
			g = gc(g, b[j])
		maxi1 = gc(g, m)
		maxi2 = gc(g, s)
		print(max(maxi1 + s, maxi2 + m))


hm = {}

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

def gcd_list(l, n):
	gcd1 = l[0]
	for i in range(1, n):
		gcd1 = gcd(gcd1, l[i])
	return gcd1
for _ in range(int(input())):
	n = int(input())
	x = [int(n) for n in input().split()]
	l2 = []
	l = list(set(x))
	n = len(l)
	if n > 2:
		hm = {}
		temp = []
		max1 = max(l[0], l[1])
		max2 = min(l[0], l[1])
		for i in range(2, len(l)):
			if l[i] > max1:
				max2 = max1
				max1 = l[i]
			elif l[i] > max2:
				max2 = l[i]
		m1 = max1
		m2 = max2
		l.remove(m1)
		l.remove(m2)
		gcd_1 = l[0]
		for i in range(1, n - 2):
			gcd_1 = gcd(gcd_1, l[i])
		s1 = gcd(gcd_1, m2) + m1
		s2 = gcd(gcd_1, m1) + m2
		print(max(s1, s2))
	elif n == 1:
		print(l[0] * 2)
	else:
		print(sum(l))


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

def gcdlist(l):
	if len(l) == 1:
		return l[0]
	else:
		num1 = l[0]
		num2 = l[1]
		gcdfinal = gcd(num1, num2)
		for i in range(2, len(l)):
			gcdfinal = gcd(gcdfinal, l[i])
		return gcdfinal
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(a[0])
	elif n == 2:
		print(a[0] + a[1])
	else:
		max1 = 0
		max2 = 0
		for i in range(1, n):
			if a[i] > max1:
				max2 = max1
				max1 = a[i]
			elif a[i] > max2 and a[i] != max1:
				max2 = a[i]
		a1 = []
		a2 = []
		for i in range(n):
			if a[i] != max1:
				a1.append(a[i])
			if a[i] != max2:
				a2.append(a[i])
		if len(a1) == 0:
			print(a[0])
		else:
			g1 = gcdlist(a1)
			g2 = gcdlist(a2)
			print(max(g1 + max1, g2 + max2))


import math
q = int(input())
while q != 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	x = set(a)
	if len(x) == 1:
		print(2 * a[0])
	else:
		b = list(x)
		k = max(b)
		b.remove(max(b))
		m = b[0]
		for i in range(len(b)):
			m = math.gcd(m, b[i])
		j = max(b)
		b.remove(max(b))
		b.append(k)
		t = b[0]
		for i in range(len(b)):
			t = math.gcd(t, b[i])
		print(max(m + k, t + j))
	q = q - 1


import math
try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = sorted(list(set(list(map(int, input().split())))))
		n = len(a)
		if n == 1:
			ans = a[0] + a[0]
		elif n == 2:
			ans = a[0] + a[1]
		else:
			temp = 0
			p1 = a[n - 1]
			p2 = a[n - 2]
			for i in range(n - 2):
				temp = math.gcd(temp, a[i])
			a1 = math.gcd(temp, p1)
			a2 = math.gcd(temp, p2)
			ans = max(a1 + p2, a2 + p1)
		print(ans)
except:
	pass


from functools import reduce

def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	var1 = max(A)
	r1 = A.count(var1)
	if r1 == N:
		print(2 * var1)
	else:
		s1 = set()
		for j in A:
			s1.add(j)
		s1.remove(var1)
		g1 = reduce(lambda x, y: gcd(x, y), s1)
		ans1 = var1 + g1
		var2 = max(s1)
		s1.remove(var2)
		s1.add(var1)
		g2 = reduce(lambda x, y: gcd(x, y), s1)
		ans2 = var2 + g2
		if ans1 >= ans2:
			print(ans1)
		else:
			print(ans2)


import math

def gc(my_list):
	result = my_list[0]
	for x in my_list[1:]:
		if result < x:
			temp = result
			result = x
			x = temp
		while x != 0:
			temp = x
			x = result % x
			result = temp
	return result
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = list(set(l))
	l.sort()
	if len(l) == 1:
		result = 2 * l[0]
	elif len(l) == 2:
		result = l[1] + l[0]
	else:
		a = l[-1]
		b = l[-2]
		l.remove(a)
		l.remove(b)
		p = gc(l)
		g1 = math.gcd(a, p)
		g2 = math.gcd(b, p)
		result = max(a + g2, b + g1)
	print(result)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) == 1:
		print(2 * a[0])
	else:
		a = list(set(a))
		(x, p) = (0, 0)
		z = max(a)
		a.remove(z)
		for i in range(len(a)):
			x = math.gcd(x, a[i])
		y = max(a)
		a.append(z)
		a.remove(y)
		for i in range(len(a)):
			p = math.gcd(p, a[i])
		print(max(z + x, p + y))


from math import gcd
for _ in range(int(input())):
	input()
	li = sorted(list(set(list((int(i) for i in input().split())))))
	if len(li) == 1:
		print(2 * li[0])
	elif len(li) == 2:
		print(sum(li))
	else:
		g = li[0]
		for i in range(1, len(li) - 2):
			g = gcd(li[i], g)
		m = gcd(g, li[-2]) + li[-1]
		n = gcd(g, li[-1]) + li[-2]
		print(max(m, n))


from math import gcd
from functools import reduce
t = int(input())
for i in range(0, t):
	m = 0
	m2 = 0
	n = int(input())
	a = [int(x) for x in input().split()]
	m = max(a)
	b = list(filter(lambda x: x != m, a))
	if b != []:
		m2 = max(b)
	c = list(filter(lambda x: x != m2, b))
	if m2 == 0:
		print(2 * m)
	else:
		g = 0
		if c != []:
			g = reduce(gcd, c)
		l = gcd(g, m)
		r = gcd(g, m2)
		print(max(l + m2, r + m))


import math

def cal_gcd(a):
	first = a[0]
	for i in range(1, len(a)):
		first = math.gcd(first, a[i])
	return first
for _ in range(int(input())):
	n = int(input())
	a = list(set(map(int, input().split())))
	n = len(a)
	if n == 1:
		print(2 * a[0])
	else:
		a.sort(reverse=True)
		b1 = a[0]
		b2 = a[1]
		if n >= 3:
			first = a[2]
			for i in range(3, len(a)):
				first = math.gcd(first, a[i])
			print(max(b1 + math.gcd(first, b2), b2 + math.gcd(first, b1)))
		else:
			print(b1 + b2)


import math
R = lambda : map(int, input().strip().split())

def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
for _ in range(int(input())):
	input()
	lst = list(set(list(R())))
	n = len(lst)
	if n == 1:
		print(2 * lst[0])
	elif n == 2:
		print(lst[0] + lst[1])
	else:
		lst.sort()
		lst_gcd = lst[0]
		for i in range(1, n - 2):
			lst_gcd = gcd(lst_gcd, lst[i])
		print(max(gcd(lst_gcd, lst[n - 2]) + lst[n - 1], gcd(lst_gcd, lst[n - 1]) + lst[n - 2]))


def gcd(a, b):
	if a == 0 or b == 0:
		return a + b
	return gcd(b, a % b)

def checkallsame(a):
	s = a[0]
	for i in range(1, len(a)):
		if a[i] != s:
			return False
	return True
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	if checkallsame(a):
		print(2 * a[0])
		continue
	a = list(set(a))
	prefixgcd = [0 for i in range(len(a))]
	suffixgcd = [0 for i in range(len(a))]
	prefixgcd[0] = a[0]
	suffixgcd[-1] = a[-1]
	for i in range(1, len(a)):
		prefixgcd[i] = gcd(a[i], prefixgcd[i - 1])
	for i in range(len(a) - 2, -1, -1):
		suffixgcd[i] = gcd(a[i], suffixgcd[i + 1])
	ans = -1
	for i in range(len(a)):
		X = a[i]
		Y = 0
		if i > 0:
			Y += prefixgcd[i - 1]
		if i < len(a) - 1:
			Y = gcd(Y, suffixgcd[i + 1])
		ans = max(ans, X + Y)
	print(ans)


from math import gcd
for t in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	li = list(set(li))
	li.sort()
	if len(li) == 1:
		print(2 * li[0])
	elif len(li) == 2:
		print(li[0] + li[1])
	else:
		mx1 = li[-1]
		mx2 = li[-2]
		gcdd = 0
		for i in range(len(li) - 2):
			gcdd = gcd(gcdd, li[i])
		print(max(mx1 + gcd(gcdd, mx2), mx2 + gcd(gcdd, mx1)))


import math

def gcd(a):
	b = min(a)
	c = int(math.sqrt(b))
	d = []
	for i in range(1, c + 1):
		if b % i == 0:
			d.append(i)
			d.append(b / i)
	d = set(d)
	d = list(d)
	d.sort()
	for i in range(len(d) - 1, -1, -1):
		j = 0
		while j < len(a):
			if a[j] % d[i] != 0:
				break
			j = j + 1
		if j == len(a):
			r = int(d[i])
			break
	return r
T = int(input())
for qwerr in range(T):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = set(a)
	b = list(b)
	b.sort()
	l = len(b)
	if l == 1:
		print(2 * b[0])
	else:
		an = []
		x = b[0:l - 1]
		y = gcd(x)
		z = b[l - 1]
		an.append(y + z)
		x = b[0:l - 2] + b[l - 1:l]
		y = gcd(x)
		z = b[l - 2]
		an.append(y + z)
		print(max(an))


from math import gcd
from functools import reduce
for testcases in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	if A.count(A[0]) == N:
		print(A[0] * 2)
	else:
		A = list(set(A))
		Highest = max(A)
		A.remove(Highest)
		gcdA_1 = reduce(gcd, A)
		IIHighest = max(A)
		A.append(Highest)
		A.remove(IIHighest)
		gcdA_2 = reduce(gcd, A)
		GCDwHighest = gcdA_1 + Highest
		GCDiiHighest = gcdA_2 + IIHighest
		print(GCDwHighest if GCDwHighest > GCDiiHighest else GCDiiHighest)


def f_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	l = list(s)
	if len(l) == 2:
		g = l[0] + l[1]
	elif len(l) == 1:
		g = 2 * l[0]
	else:
		m = max(l)
		l.remove(m)
		m1 = max(l)
		l.remove(m1)
		num1 = l[0]
		gcd = f_gcd(num1, num1)
		for i in range(1, len(l)):
			gcd = f_gcd(gcd, l[i])
		g1 = f_gcd(gcd, m)
		g2 = f_gcd(gcd, m1)
		g = max(m1 + g1, m + g2)
	print(g)


def gcd(x, y):
	if y == 0:
		return x
	if x >= y:
		return gcd(y, x % y)
	else:
		return gcd(x, y % x)
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	s = [_ for _ in set(s)]
	n = len(s)
	if n == 1:
		print(s[0] * 2)
	else:
		gcd_ord = []
		gcd_rev = []
		result = []
		gcd_ord.append(s[0])
		gcd_rev.append(s[-1])
		for i in range(1, n):
			gcd_ord.append(gcd(s[i], gcd_ord[-1]))
		for i in range(n - 2, -1, -1):
			gcd_rev.append(gcd(s[i], gcd_rev[-1]))
		gcd_rev.reverse()
		result.append(s[0] + gcd_rev[1])
		result.append(s[-1] + gcd_ord[-2])
		for i in range(1, n - 1):
			result.append(s[i] + gcd(gcd_ord[i - 1], gcd_rev[i + 1]))
		print(max(result))


from math import gcd
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	L = sorted(list(set(A)))
	if len(L) == 1:
		print(2 * L[0])
	elif len(L) == 2:
		print(L[0] + L[1])
	else:
		a1 = L[-1]
		a2 = L[-2]
		GCD = L[0]
		for i in range(1, len(L) - 2):
			GCD = gcd(GCD, L[i])
		r1 = gcd(GCD, a1) + a2
		r2 = gcd(GCD, a2) + a1
		print(max(r1, r2))


import math

def listgcd(l):
	g = l[0]
	for i in range(1, len(l)):
		g = math.gcd(l[i], g)
	return g
for _ in range(int(input())):
	n = int(input())
	s = set(map(int, input().split()))
	ll = list(s)
	if len(ll) == 1:
		print(2 * ll[0])
	else:
		max1 = max(ll)
		ll.remove(max1)
		max2 = max(ll)
		gd = max1 + listgcd(ll)
		ll.append(max1)
		ll.remove(max2)
		gd1 = max2 + listgcd(ll)
		if gd >= gd1:
			print(gd)
		else:
			print(gd1)


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

def maxsol(a):
	if len(a) <= 2:
		return sum(a)
	a = list(set(a))
	a.sort()
	k = len(a) - 1
	gcd = a[0]
	for i in range(1, len(a) - 2):
		gcd = find_gcd(gcd, a[i])
	ans1 = find_gcd(gcd, a[-1]) + a[-2]
	ans2 = find_gcd(gcd, a[-2]) + a[-1]
	return max(ans1, ans2)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print(maxsol(a))


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l = set(l)
	l = list(l)
	l.sort()
	if len(l) == 1:
		print(2 * l[0])
	elif len(l) == 2:
		print(l[0] + l[1])
	else:
		gcd1 = l[0]
		for i in range(1, len(l) - 2):
			gcd1 = math.gcd(gcd1, l[i])
		result1 = math.gcd(gcd1, l[-2]) + l[-1]
		result2 = math.gcd(gcd1, l[-1]) + l[-2]
		if result1 > result2:
			print(result1)
		else:
			print(result2)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	ar = sorted(list(set(ar)))
	if len(ar) == 1:
		m = 2 * ar[0]
	elif len(ar) == 2:
		m = ar[0] + ar[1]
	else:
		highest = ar[len(ar) - 1]
		shighest = ar[len(ar) - 2]
		g_0 = 0
		for x in range(len(ar) - 2):
			g_0 = math.gcd(g_0, ar[x])
		gh1 = math.gcd(g_0, highest)
		gh2 = math.gcd(g_0, shighest)
		m = max(highest + gh2, shighest + gh1)
	print(m)


t = int(input())

def gcd(a, b):
	if a == 0:
		return b
	if b % a == 0:
		return a
	return gcd(b % a, a)
while t:
	n = int(input())
	l = [int(x) for x in input().split()]
	ls = list(dict.fromkeys(l))
	ls.sort(reverse=True)
	if len(ls) == 1:
		print(2 * ls[0])
	elif len(ls) == 2:
		print(ls[0] + ls[1])
	else:
		ans1 = ls[0]
		ans2 = ls[1]
		for i in range(2, len(ls)):
			ans1 = gcd(ans1, ls[i])
		for i in range(2, len(ls)):
			ans2 = gcd(ans2, ls[i])
		print(max(ans1 + ls[1], ans2 + ls[0]))
	t = t - 1


import math
t = int(input())
for i in range(0, t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = set(l)
	l1 = list(l1)
	n1 = len(l1)
	m1 = min(l1)
	m2 = max(l1)
	l1.sort()
	if n1 == 1:
		print(2 * m2)
	elif n1 == 2:
		print(m1 + m2)
	else:
		for j in range(n1 - 1, -1, -1):
			if l1[j] != m2:
				m3 = l1[j]
				break
		g1 = l1[0]
		for j in range(0, n1):
			if l1[j] != m3:
				g1 = math.gcd(g1, l1[j])
		g1 += m3
		g = l1[0]
		for j in range(0, n1):
			if l1[j] != m2:
				g = math.gcd(g, l1[j])
		g += m2
		if g > g1:
			print(g)
		else:
			print(g1)


import sys
from math import gcd

def read_line():
	return sys.stdin.readline().split()

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

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]
t = read_int()
for test in range(t):
	read_int()
	a = {int(x) for x in read_line()}
	a = list(a)
	n = len(a)
	pre = []
	post = []
	gcdPre = 0
	pre.append(0)
	for i in range(1, n):
		gcdPre = gcd(gcdPre, a[i - 1])
		pre.append(gcdPre)
	gcdPost = 0
	post.append(0)
	for i in range(n - 2, -1, -1):
		gcdPost = gcd(gcdPost, a[i + 1])
		post.append(gcdPost)
	post.reverse()
	gcd1 = 0
	gcdMax = 0
	for i in range(n):
		gcdMax = max(gcdMax, a[i] + gcd(pre[i], post[i]))
	if n == 1:
		print(2 * gcdMax)
	else:
		print(gcdMax)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 2:
		print(arr[0] + arr[1])
		continue
	arr.sort()
	i = 0
	for j in range(1, n):
		if arr[i] == arr[j]:
			continue
		else:
			i += 1
			arr[i] = arr[j]
	n = i + 1
	curr_gcd = arr[0]
	for i in range(1, n - 2):
		curr_gcd = gcd(curr_gcd, arr[i])
	a = gcd(curr_gcd, arr[n - 2]) + arr[n - 1]
	b = gcd(curr_gcd, arr[n - 1]) + arr[n - 2]
	if a > b:
		print(a)
	else:
		print(b)


import math
import bisect

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

def inn():
	return int(input())

def inl():
	return list(map(int, input().split()))
MOD = 10 ** 9 + 7
INF = inf = 10 ** 18 + 5
for t in range(int(input())):
	n = inn()
	a = list(map(int, input().split()))
	a = list(set(a))
	n = len(a)
	if n == 1:
		print(2 * a[0])
		continue
	pre_gcd = [1] * n
	suf_gcd = [1] * n
	pre_gcd[0] = a[0]
	for i in range(1, n):
		pre_gcd[i] = math.gcd(pre_gcd[i - 1], a[i])
	suf_gcd[n - 1] = a[n - 1]
	for i in range(n - 2, -1, -1):
		suf_gcd[i] = math.gcd(suf_gcd[i + 1], a[i])
	mgcd = max(a[0] + suf_gcd[1], a[n - 1] + pre_gcd[n - 2])
	for i in range(1, n - 1):
		mgcd = max(mgcd, a[i] + math.gcd(pre_gcd[i - 1], suf_gcd[i + 1]))
	print(mgcd)


def gcd(num1, num2):
	if num2 == 0:
		return num1
	return gcd(num2, num1 % num2)
tests = int(input())
for test in range(tests):
	n = int(input())
	numList = list(set(map(int, input().strip().split())))
	leftList = []
	rightList = []
	if len(numList) == 1 and len(numList) != n:
		print(numList[0] * 2)
	else:
		leftList.append(numList[0])
		rightList.append(numList[::-1][0])
		for i in range(len(numList) - 1):
			leftList.append(gcd(leftList[i], numList[i + 1]))
		numList.reverse()
		for i in range(len(numList) - 1):
			rightList.append(gcd(rightList[i], numList[i + 1]))
		numList.reverse()
		rightList.reverse()
		temp = 0
		maxGCD = 0
		j = k = 0
		for i in range(len(numList)):
			if i == 0:
				temp = numList[i] + rightList[i + 1]
			elif i == len(numList) - 1:
				temp = numList[i] + leftList[i - 1]
			else:
				temp = numList[i] + gcd(leftList[i - 1], rightList[i + 1])
			if temp > maxGCD:
				maxGCD = temp
		print(maxGCD)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
for t in range(int(input())):
	n = int(input())
	a = set(map(int, input().strip().split(' ')))
	a = list(a)
	if len(a) == 1:
		print(2 * a[0])
	else:
		l = a
		l.sort()
		maxvalue1 = l[len(l) - 1]
		result = a[0]
		for i in range(1, len(a)):
			if a[i] != maxvalue1:
				result = gcd(a[i], result)
		maxvalue1 = maxvalue1 + result
		maxvalue2 = l[len(l) - 2]
		result = a[0]
		for i in range(1, len(a)):
			if a[i] != maxvalue2:
				result = gcd(a[i], result)
		maxvalue2 = maxvalue2 + result
		print(max(maxvalue1, maxvalue2))


import math
T = int(input())
for j in range(T):
	n = int(input())
	A = list(set(map(int, input().split())))
	A.sort()
	n_1 = len(A)
	if n_1 == 1:
		print(2 * A[0])
	else:
		gcd_a = A[0]
		gcd_b = A[-1]
		for i in range(1, n_1):
			gca_A_a = math.gcd(gcd_a, A[i])
			gca_B_b = math.gcd(gcd_b, A[i])
			gca_c = math.gcd(gcd_a, gcd_b)
			op1 = gca_A_a + gcd_b
			op2 = gca_B_b + gcd_a
			op3 = gca_c + A[i]
			max_op = max(op1, op2, op3)
			if op1 == max_op:
				gcd_a = gca_A_a
			elif op2 == max_op:
				gcd_b = gca_B_b
			else:
				gcd_a = gca_c
				gcd_b = A[i]
		print(gcd_a + gcd_b)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = sorted(list(set(map(int, input().strip().split()))))
	length = len(arr)
	if length == 1:
		print(2 * arr[0])
	elif length == 2:
		print(arr[0] + arr[1])
	else:
		g_0 = arr[0]
		highest = arr[-1]
		shighest = arr[-2]
		for i in arr[:length - 2]:
			g_0 = math.gcd(g_0, i)
		gh1 = math.gcd(g_0, highest) + shighest
		gh2 = math.gcd(g_0, shighest) + highest
		print(max(gh1, gh2))


from math import *
t = int(input())

def func(l, large, large2):
	gcdVal = 0
	for x in range(0, n - 2):
		gcdVal = gcd(gcdVal, l[x])
	value1 = gcd(gcdVal, large)
	value2 = gcd(gcdVal, large2)
	ans = max(large + value2, large2 + value1)
	return ans
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(list(set(l)))
	n = len(l)
	if n == 1:
		ans = 2 * l[0]
	else:
		large = l[n - 1]
		large2 = l[n - 2]
		ans = func(l, large, large2)
	print(ans)


import sys
import math
strInp = lambda : input().strip().split()
intInp = lambda : list(map(int, strInp()))

def GCD(x, y):
	return math.gcd(x, y)
for t in range(int(input())):
	n = int(input())
	arr = list(set(intInp()))
	if len(arr) == 1:
		print(arr[0] * 2)
	else:
		prefixGcd = [arr[0]]
		for i in range(1, len(arr)):
			prefixGcd.append(GCD(prefixGcd[-1], arr[i]))
		suffixGcd = [arr[-1]]
		for i in range(len(arr) - 1, -1, -1):
			suffixGcd.append(GCD(suffixGcd[-1], arr[i]))
		suffixGcd.reverse()
		m = arr[0] + suffixGcd[1]
		m = max(m, arr[-1] + prefixGcd[-2])
		for i in range(1, len(arr) - 1):
			m = max(m, arr[i] + GCD(prefixGcd[i - 1], suffixGcd[i + 1]))
		print(m)


from math import gcd
from functools import reduce
for _ in range(int(input())):
	ans = 0
	n = int(input())
	a = list(map(int, input().split()))
	a = list(set(a))
	if len(a) == 1:
		print(a[0] * 2)
		continue
	for i in range(len(a)):
		k = a[i]
		del a[i]
		ans = max(ans, k + reduce(gcd, a))
		a.insert(i, k)
	print(ans)


import itertools

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	ma = 0
	if len(set(l)) == 1:
		print(l[0] * 2)
	else:
		k = list(set(l))
		k = sorted(k)
		for i in range(len(k) - 2, len(k)):
			j = k[i]
			b = []
			for o in range(0, len(k)):
				if k[o] != j:
					b.append(k[o])
			if len(b) == 1:
				v = b[0]
			else:
				num1 = b[0]
				num2 = b[1]
				v = find_gcd(num1, num2)
				for p in range(2, len(b)):
					v = find_gcd(v, b[p])
			ma = max(ma, v + j)
		print(ma)
	t -= 1


from math import gcd
from functools import reduce
t = int(input())
for i in range(t):
	n = int(input())
	ll = list(map(int, input().split()))
	ss = set(ll)
	mx = max(ss)
	ns = ss - {mx}
	if len(ll) >= 2 and len(ss) == 1:
		print(mx * 2)
	elif len(ll) >= 2 and len(ss) == 2:
		print(sum(ss))
	else:
		(a, b) = (list(sorted(ss))[-1], list(sorted(ss))[-2])
		print(max(reduce(gcd, ss - {a}) + a, reduce(gcd, ss - {b}) + b))


import math
from fractions import gcd
from functools import reduce

def find_gcd(list):
	x = reduce(gcd, list)
	return x
t = int(input(''))
fin = []
sums = [0, 0, 0]
for v in range(t):
	n = int(input(''))
	a = input('').split(' ')
	rmap = map(int, a)
	a = list(rmap)
	a.sort()
	t = a[0]
	o = []
	o.append(t)
	for i in range(n):
		if t != a[i]:
			o.append(a[i])
			t = a[i]
	N = len(o)
	if len(o) == 1:
		fin.append(2 * o[0])
	elif len(o) == 2:
		fin.append(o[0] + o[1])
	else:
		g = find_gcd(o[0:len(o) - 2])
		fin.append(max(o[N - 1] + gcd(g, o[N - 2]), o[N - 2] + gcd(g, o[N - 1])))
for i in fin:
	print(i)