import heapq
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    A = [-A[i] for i in range(N)]
    heapq.heapify(A)
    if len(A)==1:
        ans = 1
    else:
        ans = 0
        while len(A)>1:
            a = -heapq.heappop(A)
            b = -heapq.heappop(A)
            ans += 2*b
            if a>b:
                heapq.heappush(A,-(a-b))
        if A:
            ans += 1
    print(ans)