from math import gcd
from itertools import permutations
def calculate_gcd_of_list(lst):
if len(lst) == 0:
return 0
current_gcd = lst[0]
for num in lst[1:]:
current_gcd = gcd(current_gcd, num)
return current_gcd
def max_gcd_sum(N, A):
max_sum = 0
all_permutations = permutations(A)
for perm in all_permutations:
odd_indices = perm[0:N:2]
even_indices = perm[1:N:2]
X = calculate_gcd_of_list(odd_indices)
Y = calculate_gcd_of_list(even_indices)
max_sum = max(max_sum, X + Y)
return max_sum
def main():
import sys
input = sys.stdin.read
data = input().split()
index = 0
T = int(data[index])
index += 1
results = []
for _ in range(T):
N = int(data[index])
index += 1
A = list(map(int, data[index:index + N]))
index += N
results.append(max_gcd_sum(N, A))
for result in results:
print(result)