def solve():
    T = int(input())
    results = []
    
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        
        # مرتب‌سازی بر اساس قدر مطلق نزولی
        A.sort(key=lambda x: abs(x), reverse=True)
        
        S = 0
        temp_list=[]
        # نوبت‌ها را یکی در میان به Roy و Hridoy اختصاص می‌دهیم
        for i in range(N):
            if i % 2 == 0:  # نوبت Roy (جمع می‌کند)
                S += A[i]
            else:           # نوبت Hridoy (کم می‌کند)
                S -= A[i]
            if i >=1:
              temp_list.append((S,i))
        S =  max(temp_list, key=lambda x: x[0])

        
        results.append(str(S))
    
    print('\n'.join(results))

solve()