import sys

input = lambda: sys.stdin.readline().strip()

def print(value):
    sys.stdout.write(str(value) + '\n')

def printl(l):
    print(''.join(str(y) for y in l))

def rl():
    return(map(int,input().split()))

for _ in range(int(input())):
    n=int(input())
    a=list(rl())

    a.sort()
    s=n
    e=0

    for i in range(n):
        if (n-i)%2:
            e-=a[i]
            if e>=0:
                s=n-i-1
                e=0
        else:
            e+=a[i]
            if e<=0:
                s=n-i-1
                e=0
    a.reverse()
    e=0
    for i in range(s):
        if i%2:
            e-=a[i]
        else:
            e+=a[i]
    
    print(e)