# ruff: noqa: E731, E741
from math import inf
import sys

read = sys.stdin.readline
input = lambda: read().rstrip()
ir = lambda: int(read())
rir = lambda: range(int(read()))
mir = lambda: map(int, read().split())
lmir = lambda: list(map(int, read().split()))


def solve():
    n = ir()
    a = sorted(mir())
    s = sum(a[-1::-2]) - sum(a[-2::-2])
    if n == 2:
        print(s)
        return
    roy = hridoy = s
    roy_turn = n % 2 == 1
    for ai in a[:-2]:
        # print(roy, hridoy, s, "roy" if roy_turn else "hridoy")
        if roy_turn:
            s -= ai
            roy = max(hridoy, s)
        else:
            s += ai
            hridoy = min(roy, s)
        roy_turn = not roy_turn
    # print(roy, hridoy, s)
    print(roy)
    # print()


def main():
    for _ in rir():
        solve()


def test():
    pass


if __name__ == "__main__":
    if sys.stdin.isatty():
        test()
    else:
        main()