T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    mini = 10**18
    csum = 0
    flag = True
    for i in range(N-1,-1,-1):
        if A[i]<=0:
            break
        if flag:
            csum += A[i]
            flag = not flag
        else:
            mini = min(mini,csum)
            csum -= A[i]
            flag = not flag
    mini = min(mini,csum)
    print(mini if mini!=10**18 else 0)