for _ in range(int(input())):
    n = int(input())
    a = sorted(map(int, input().split()))
    d = [y - x for x, y in zip(a, a[1:])]
    d.sort(reverse=True)
    if n % 2:
        ans = a[0] + sum(d[::2])
    else:
        ans = a[-1] - (a[0] + sum(d[:n-2:2]))
    print(ans)