One important contest will take place on the most famous programming platform (Topforces) very soon!

The authors have a pool of $n$ problems and should choose at most three of them into this contest. The prettiness of the $i$-th problem is $a_i$. The authors have to compose the most pretty contest (in other words, the cumulative prettinesses of chosen problems should be maximum possible).

But there is one important thing in the contest preparation: because of some superstitions of authors, the prettinesses of problems cannot divide each other. In other words, if the prettinesses of chosen problems are $x, y, z$, then $x$ should be divisible by neither $y$, nor $z$, $y$ should be divisible by neither $x$, nor $z$ and $z$ should be divisible by neither $x$, nor $y$. If the prettinesses of chosen problems are $x$ and $y$ then neither $x$ should be divisible by $y$ nor $y$ should be divisible by $x$. Any contest composed from one problem is considered good.

Your task is to find out the maximum possible total prettiness of the contest composed of at most three problems from the given pool.

You have to answer $q$ independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

The first line of the query contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of problems.

The second line of the query contains $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the prettiness of the $i$-th problem.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$.


-----Output-----

For each query print one integer — the maximum possible cumulative prettiness of the contest composed of at most three problems from the given pool of problems in the query.


-----Example-----
Input
3
4
5 6 15 30
4
10 6 30 15
3
3 4 6

Output
30
31
10

Difficulty: HARD
Tags: Sorting

Mathematics

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
def calc(X, Y):
	if len(Y) == 3:
		return sum(Y)
	for x in X:
		for y in Y:
			if y % x == 0:
				break
		else:
			return calc([i for i in X if i != x], sorted(Y + [x])[::-1])
	return sum(Y)
for _ in range(int(input())):
	N = int(input())
	A = sorted(set([int(a) for a in input().split()]))[::-1]
	print(max(calc(A, []), calc(A[1:], [])))


def calcSum(first):
	nonlocal m
	s = m[first]
	k = 1
	for i in range(first + 1, len(m)):
		yes = True
		for j in range(first, i):
			if m[j] % m[i] == 0:
				yes = False
				break
		if yes:
			s += m[i]
			k += 1
			if k == 3:
				break
	return s
import sys
nnn = int(input())
for _ in range(nnn):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	if n == 1:
		print(a[0])
		continue
	if n == 2:
		if a[0] % a[1] == 0 or a[1] % a[0] == 0:
			print(max(a))
		else:
			print(sum(a))
		continue
	a.sort(reverse=True)
	m = [a[0]]
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			continue
		yes = True
		for j in range(1, len(m)):
			if m[j] % a[i] == 0:
				yes = False
				break
		if yes:
			m.append(a[i])
			if len(m) >= 10:
				break
	s1 = calcSum(0)
	if len(m) > 1:
		s2 = calcSum(1)
	else:
		s2 = 0
	s = max(s1, s2)
	print(s)


3.6
import sys

def eprint(*args, **kwargs):
	if __debug__:
		print(*args, file=sys.stderr, **kwargs)

def __starting_point():
	q = int(input())
	while q > 0:
		ans = 0
		q -= 1
		x = y = z = 0
		n = int(input())
		arr = list(set(map(int, input().split(' '))))
		arr.sort()
		if arr == [2, 3, 5]:
			print(10)
			continue
		z = arr[len(arr) - 1]
		if z % 2 == 0 and z % 3 == 0 and (z % 5 == 0) and (arr.count(z // 2) > 0) and (arr.count(z // 3) > 0) and (arr.count(z // 5) > 0):
			ans = max(ans, z // 2 + z // 3 + z // 5)
		res = []
		while len(arr) > 0 and len(res) < 3:
			c = arr.pop()
			flag = 1
			for x in res:
				flag &= x % c != 0
			if flag == 1:
				res.append(c)
		ans = max(ans, sum(res))
		print(ans)
__starting_point()


M = lambda : list(map(int, input().split()))
q = int(input())
for qer in range(q):
	n = int(input())
	a = M()
	D = {}
	for i in a:
		D[i] = 1
	a.sort(reverse=True)

	def get_max():
		for i in a:
			if D[i]:
				return i
		return 0

	def fix(x):
		for i in a:
			if x % i == 0:
				D[i] = 0
	L = [0] * 3
	for i in range(3):
		L[i] = get_max()
		if L[i] == 0:
			break
		fix(L[i])
	ans = sum(L)
	if a[0] % 2 == 0 and a[0] % 3 == 0 and (a[0] % 5 == 0):
		if a[0] / 2 in D and a[0] / 3 in D and (a[0] / 5 in D):
			ans = max(ans, a[0] // 2 + a[0] // 3 + a[0] // 5)
	print(ans)


def solve(a_s):
	a_s = set(a_s)
	n = max(a_s)
	largest = n
	if n // 2 in a_s and n // 3 in a_s and (n // 5 in a_s):
		largest = n // 2 + n // 3 + n // 5
	m = []
	for _ in range(3):
		if not a_s:
			break
		n = max(a_s)
		a_s = set([j for j in a_s if n % j != 0])
		m.append(n)
		if sum(m) > largest:
			largest = sum(m)
	return largest
q = int(input())
for _ in range(q):
	n = int(input())
	a_s = list(map(int, input().split()))
	print(solve(a_s))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [0, 0] + sorted(set(map(int, input().split())))
	ans = a[-1]
	for z in range(len(a) - 1, 1, -1):
		y = z - 1
		while a[y] > 0 and a[z] % a[y] == 0:
			y -= 1
		x = y - 1
		while a[x] > 0 and (a[z] % a[x] == 0 or a[y] % a[x] == 0):
			x -= 1
		ans = max(ans, a[x] + a[y] + a[z])
	print(ans)


from sys import stdin
from itertools import tee

def input():
	return stdin.readline()

def remove_divisors(x, xs):
	return [y for y in xs if y % xs != 0]
q = int(input())
for _ in range(q):
	n = int(input())
	aas = list(set(map(int, input().split())))
	aas.sort(reverse=True)
	ulim2 = list(map(sum, zip(aas[:-1], aas[1:]))) + [0]
	ulim3 = list(map(sum, zip(aas[:-2], ulim2[1:]))) + [0, 0]
	it1 = iter(zip(aas, ulim3, ulim2))
	answer = 0
	try:
		while True:
			(a, u3, _) = next(it1)
			if u3 < answer:
				break
			(it1, it2) = tee(it1)

			def f1(i):
				(b, _, _) = i
				return a % b != 0
			it2 = filter(f1, it2)
			tsum = 0
			try:
				while True:
					(b, _, u2) = next(it2)
					if u2 < tsum:
						break
					(it2, it3) = tee(it2)

					def f2(i):
						(c, _, _) = i
						return b % c != 0
					it3 = filter(f2, it3)
					(c, _, _) = next(it3, (0, 0, 0))
					tsum = max(tsum, b + c)
			except StopIteration:
				pass
			answer = max(answer, a + tsum)
	except StopIteration:
		pass
	print(answer)


import sys
input = sys.stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	ls = list(map(int, input().strip().split()))
	ls = list(set(ls))
	ls.sort()
	n = len(ls)
	if n == 1:
		print(ls[0])
	elif n == 2:
		if ls[1] % ls[0] == 0:
			print(ls[1])
		else:
			print(ls[0] + ls[1])
	else:
		ans = []
		for i in range(n - 1, n - 1 - 3, -1):
			c = i
			for j in range(c - 1, -1, -1):
				if ls[c] % ls[j] != 0:
					b = j
					break
			else:
				ans.append(ls[c])
				continue
			for k in range(b - 1, -1, -1):
				if ls[c] % ls[k] != 0 and ls[b] % ls[k] != 0:
					a = k
					break
			else:
				ans.append(ls[c] + ls[b])
				continue
			ans.append(ls[c] + ls[b] + ls[a])
		print(max(ans))


q = int(input())
ans = []
for w in range(q):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	a = a[::-1]
	a1 = 0
	b1 = 0
	c1 = 0
	a1 = a[0]
	for i in range(n):
		if a1 % a[i] != 0:
			b1 = a[i]
			break
	for i in range(n):
		if a1 % a[i] != 0 and b1 % a[i] != 0:
			c1 = a[i]
			break
	a2 = 0
	b2 = 0
	c2 = 0
	if a1 % 2 == 0:
		for i in range(n):
			if a[i] == a1 // 2:
				a2 = a[i]
				break
	if a1 % 3 == 0:
		for i in range(n):
			if a[i] == a1 // 3:
				b2 = a[i]
				break
	if a1 % 5 == 0:
		for i in range(n):
			if a[i] == a1 // 5:
				c2 = a[i]
				break
	ans.append(max(a1 + b1 + c1, a2 + b2 + c2))
for i in range(q):
	print(ans[i])


for i in range(int(input())):
	n = int(input())
	w = set()
	[w.add(int(j)) for j in input().split()]
	data = list(w)
	data.sort()
	nums = [data[-1]]
	ind = len(data) - 2
	cnt = 1
	while ind >= 0:
		if cnt == 1:
			if nums[0] % data[ind] != 0:
				nums.append(data[ind])
				cnt += 1
		elif nums[0] % data[ind] != 0 and nums[1] % data[ind] != 0:
			nums.append(data[ind])
			break
		ind -= 1
	ans = sum(nums)
	if len(data) >= 2:
		nums2 = [data[-2]]
		ind = len(data) - 3
		cnt = 1
		while ind >= 0:
			if cnt == 1:
				if nums2[0] % data[ind] != 0:
					nums2.append(data[ind])
					cnt += 1
			elif nums2[0] % data[ind] != 0 and nums2[1] % data[ind] != 0:
				nums2.append(data[ind])
				break
			ind -= 1
		ans = max(ans, sum(nums2))
	print(ans)


import sys
q = int(input())
lines = sys.stdin.readlines()
res = []

def getMax(numset):
	n = max(numset)
	numset = set([j for j in numset if n % j != 0])
	return (n, numset)
for i in range(q):
	n = int(lines[2 * i])
	m = []
	numset = set()
	for j in lines[2 * i + 1].split():
		numset.add(int(j))
	total = max(numset)
	n = total
	if n // 2 in numset and n // 3 in numset and (n // 5 in numset):
		total = n // 2 + n // 3 + n // 5
	for _ in range(3):
		if len(numset) == 0:
			break
		(n, numset) = getMax(numset)
		m.append(n)
		if sum(m) > total:
			total = sum(m)
	res.append(str(total))
print('\n'.join(res))


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	__ = int(stdin.readline())
	a = sorted(set(map(int, stdin.readline().split())), reverse=True)
	s = a[0]
	n = len(a)
	for i in range(n):
		el = a[i]
		for j in range(i + 1, n):
			if el % a[j] != 0:
				s = max(s, el + a[j])
				el1 = a[j]
				for k in range(j + 1, n):
					if el1 % a[k] != 0 and el % a[k] != 0:
						s = max(s, el + el1 + a[k])
						break
				break
	stdout.write(f'{s}\n')


def find(A):
	if len(A) == 0:
		return 0
	checked = [0] * len(A)
	temp = []
	for i in range(len(A)):
		if len(temp) < 3 and checked[i] == 0:
			temp += [A[i]]
			for j in range(i + 1, len(A)):
				if A[i] % A[j] == 0:
					checked[j] = 1
		if len(temp) == 3:
			break
	return sum(temp)
from collections import defaultdict
for _ in range(int(input())):
	input()
	dic = defaultdict(int)
	A = list(map(int, input().strip().split(' ')))
	for i in range(len(A)):
		dic[A[i]] = 0
	A = sorted([x for x in dic], reverse=True)
	print(max(find(A), find(A[1:]), find(A[2:]), find(A[3:])))


import sys
input = sys.stdin.readline
q = int(input())
for testcase in range(q):
	n = int(input())
	A = sorted(set(map(int, input().split())), reverse=True)
	L = len(A)
	ANS = A[0]
	for i in range(L):
		NOW0 = A[i]
		NOW1 = 0
		flag = 0
		for j in range(i + 1, L):
			if NOW0 % A[j] != 0:
				NOW1 = A[j]
				ANS = max(ANS, NOW0 + NOW1)
				for k in range(j + 1, L):
					if NOW0 % A[k] != 0 and NOW1 % A[k] != 0:
						ANS = max(ANS, NOW0 + NOW1 + A[k])
						break
				break
	print(ANS)


q = int(input())
for w in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = list(set(arr))
	arr.sort(reverse=True)
	n = len(arr)
	ans = 0
	for i in range(n):
		ans = max(ans, arr[i])
		for j in range(i + 1, n):
			if arr[i] % arr[j] != 0:
				ans = max(ans, arr[i] + arr[j])
				if j + 1 < n and ans >= arr[i] + arr[j + 1] + arr[j]:
					break
				for k in range(j + 1, n):
					if ans >= arr[i] + arr[j] + arr[k]:
						break
					if arr[j] % arr[k] != 0 and arr[i] % arr[k] != 0:
						ans = max(ans, arr[i] + arr[j] + arr[k])
	print(ans)


q = int(input())
for query in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	wy = -1000000000000
	a = [l[0]]
	u = 1
	while u < n:
		if l[u] != l[u - 1]:
			a.append(l[u])
		if len(a) > 4:
			break
		u += 1
	if len(a) > 3 and a[1] == a[0] / 2 and (a[2] == a[0] / 3) and (a[3] == a[0] / 5) or (len(a) > 4 and a[1] == a[0] / 2 and (a[2] == a[0] / 3) and (a[3] == a[0] / 4) and (a[4] == a[0] / 5)):
		wy = a[1] + a[2] + a[3]
	nowa = [l[i] for i in range(n) if l[0] % l[i] != 0]
	nowa.sort()
	nowa.reverse()
	if len(nowa) > 0:
		part = 0
		for i in range(1, len(nowa)):
			if nowa[0] % nowa[i] != 0:
				part = nowa[i]
				break
		wyn = l[0] + nowa[0] + part
	else:
		wyn = l[0]
	print(max(wyn, wy))


T = int(input())
for o in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = []
	for i in a:
		if len(b) == 0 or (len(b) != 0 and b[-1] != i):
			b.append(i)
	a = b
	n = len(b)
	if n == 1:
		print(a[0])
	elif n == 2:
		if a[1] % a[0] == 0:
			print(a[1])
		else:
			print(a[0] + a[1])
	else:
		ans1 = a[-1]
		for i in reversed(range(0, n - 1)):
			if a[-1] % a[i] != 0:
				ans1 += a[i]
				for j in reversed(range(0, i)):
					if a[-1] % a[j] != 0 and a[i] % a[j] != 0:
						ans1 += a[j]
						break
				break
		ans2 = a[-2]
		for i in reversed(range(0, n - 2)):
			if a[-2] % a[i] != 0:
				ans2 += a[i]
				for j in reversed(range(0, i)):
					if a[-2] % a[j] != 0 and a[i] % a[j] != 0:
						ans2 += a[j]
						break
				break
		print(max(ans1, ans2))


for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	a = sorted(list(set(a)))
	ans = max(a)
	n = len(a)
	for i in range(n):
		(x, y, z) = (0, 0, a[i])
		for j in reversed(range(i)):
			if not y:
				if z % a[j] != 0:
					y = a[j]
			elif not x:
				if z % a[j] != 0 and y % a[j] != 0:
					x = a[j]
			else:
				break
			ans = max(ans, x + y + z)
	print(ans)


from sys import stdin, stdout
q = int(stdin.readline())
for it in range(q):
	n = int(stdin.readline())
	a = set(map(int, stdin.readline().split()))
	M = max(a)
	if M % 30 == 0 and M // 2 in a and (M // 3 in a) and (M // 5 in a):
		p1 = M * 31 // 30
	else:
		p1 = 0
	ans = [M]
	a = sorted(list(a))
	idx = len(a) - 2
	while idx >= 0 and len(ans) < 3:
		if any([x % a[idx] == 0 for x in ans]):
			idx -= 1
			continue
		ans.append(a[idx])
		idx -= 1
	p2 = sum(ans)
	if p1 > p2:
		stdout.write(str(p1) + '\n')
	else:
		stdout.write(str(p2) + '\n')


t = int(input())
for _ in range(t):
	n = int(input())
	ns = list(map(int, input().split()))
	ns.sort(reverse=True)
	from collections import OrderedDict
	ns = list(OrderedDict.fromkeys(ns))
	m = ns[0]
	ans = m
	if m % 30 == 0 and m // 2 in ns and (m // 3 in ns) and (m // 5 in ns):
		ans = m // 30 * 31
	c = m
	for i in range(len(ns)):
		if m % ns[i] != 0:
			c += ns[i]
			for j in range(i + 1, len(ns)):
				if m % ns[j] != 0 and ns[i] % ns[j] != 0:
					c += ns[j]
					break
			break
	ans = max(ans, c)
	print(ans)


q = int(input())
for w in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = list(set(arr))
	arr.sort(reverse=True)
	n = len(arr)
	ansarr = [-1 for i in range(n)]
	maxans = 0
	for i in range(n):
		currans = arr[i]
		for j in range(i + 1, min(i + 171, n)):
			if arr[i] % arr[j] != 0:
				currans = max(currans, arr[i] + arr[j])
				if j + 1 < n and arr[i] + arr[j] + arr[j + 1] <= maxans:
					break
				for k in range(j + 1, min(j + 171, n)):
					if arr[j] % arr[k] != 0 and arr[i] % arr[k] != 0:
						currans = max(currans, arr[i] + arr[j] + arr[k])
						if currans <= maxans:
							break
		ansarr[i] = currans
		maxans = max(maxans, currans)
	print(max(ansarr))


def cal(sorted_list, size):
	max_sum = 0
	for k in range(len(sorted_list)):
		max_sum = max(sorted_list[k], max_sum)
		for i in range(k + 1, size):
			temp_1 = sorted_list[i]
			if sorted_list[k] % temp_1 != 0:
				if i + 1 < size and max_sum >= sorted_list[k] + sorted_list[i] + sorted_list[i + 1]:
					break
				check_sum = sorted_list[k] + temp_1
				max_sum = max(max_sum, check_sum)
				for j in range(i + 1, size):
					if max_sum >= sorted_list[k] + sorted_list[i] + sorted_list[j]:
						break
					temp_2 = sorted_list[j]
					if sorted_list[k] % temp_2 != 0 and temp_1 % temp_2 != 0:
						max_sum = max(max_sum, check_sum + temp_2)
						break
	return max_sum

def solve():
	no_querries = int(input())
	output = []
	for i in range(no_querries):
		size = int(input())
		alist_raw = input().split()
		alist = [int(x) for x in alist_raw]
		alist.sort(reverse=True)
		alist = unique(alist)
		output.append(cal(alist, len(alist)))
	for x in output:
		print(x)

def unique(alist):
	unique = [alist[0]]
	for i in range(1, len(alist)):
		if alist[i] < unique[len(unique) - 1]:
			unique.append(alist[i])
	return unique
solve()


q = int(input())
for _ in range(q):
	e = set()
	n = int(input())
	a = sorted(map(int, input().split()))[::-1]
	for x in a:
		e.add(x)
	r = []
	for k in a:
		for c in r:
			if c % k == 0:
				break
		else:
			r.append(k)
		if len(r) >= 3:
			break
	m = r[0]
	if m % 30 == 0 and m // 2 in e and (m // 3 in e) and (m // 5 in e) and (m // 30 * 31 > sum(r)):
		print(m // 30 * 31)
	else:
		print(sum(r))


q = int(input())
for i in range(q):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort(reverse=True)
	first = a[0]
	second = -1
	third = -1
	maxa = a[0]
	arr = []
	for i in range(n):
		if first % a[i] != 0:
			if second == -1:
				second = a[i]
			elif second % a[i] != 0:
				if third == -1:
					third = a[i]
				else:
					break
	if maxa % 30 == 0:
		if maxa // 2 in a and maxa // 3 in a and (maxa // 5 in a):
			print(max(first + max(second, 0) + max(third, 0), maxa // 2 + maxa // 3 + maxa // 5))
		else:
			print(max(first, 0) + max(second, 0) + max(third, 0))
	else:
		print(max(first, 0) + max(second, 0) + max(third, 0))


answer = []
for _ in range(int(input())):
	input()
	l = sorted(map(int, input().split()))
	other = 0
	if l[-1] % 30 == 0 and len(set(l) & {l[-1] // 2, l[-1] // 3, l[-1] // 5}) == 3:
		other = 31 * l[-1] // 30
	while len(l) >= 2 and l[-1] % l[-2] == 0:
		del l[-2]
	while len(l) >= 3 and 0 in (l[-1] % l[-3], l[-2] % l[-3]):
		del l[-3]
	answer.append(str(max(other, sum(l[-3:]))))
print('\n'.join(answer))