import sys

# sys.setrecursionlimit(10 ** 9)  # Codeforcesでは350000程度に


def input():
    return sys.stdin.readline().strip()


t = int(input())
for i in range(t):
    n = int(input())
    A = list(map(int, input().split()))

    A.sort(reverse=True)
    ans = 0
    if n % 2 == 0:
        for j in range(n // 2):
            ans += A[2 * j] - A[2 * j + 1]
    else:
        mid = n // 2
        ans = A[mid]
        ans_now = 0
        for j in range(n // 2):
            ans_now += A[2 * j] - A[2 * j + 1]
            mid += 1
            # print(mid)
            ans = max(ans, ans_now + A[mid])
    print(ans)