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)