import sys
from itertools import *
from bisect import *
from collections import *
from math import gcd
import heapq

input = lambda: sys.stdin.readline().rstrip("\r\n")
rint = lambda: int(input())
rlist = lambda: list(map(int, input().split()))
rgrid = lambda n: [rlist() for _ in range(n)]

fmin = lambda x, y: x if x < y else y
fmax = lambda x, y: x if x > y else y
# MOD = 998244353
MOD = 10**9 + 7
INF = float("inf")


def solve():
    N = rint()
    A = rlist()
    A.sort(reverse=True)
    P = [0] * (N + 1)
    for i, x in enumerate(A):
        P[i + 1] = P[i] + (-x if i & 1 else x)

    v = P[N]
    for k in range(N - 1, 1, -1):
        if k & 1:
            v = fmin(P[k], v)
        else:
            v = fmax(P[k], v)
    return v


TT = 1
TT = rint()
for tc in range(TT):
    ans = solve()

    print(ans)
    # print(*ans)
    # print("Yes" if ans else "No")