T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = A[-1]-A[-2]
    A.pop()
    A.pop()
    flag = True
    for i in range(len(A)-1,-1,-1):
        if A[i]<=0:
            break
        if flag:
            ans += A[i]
            flag = not flag
        else:
            ans -= A[i]
            flag = not flag
    print(ans)