#include <bits/stdc++.h>     //   All praise is due to Allah alone, and peace and blessings be
using namespace std;         //         upon him, after whom there is no other Prophet.

int32_t main() {
    cin.tie(0)->sync_with_stdio(false);

    function<void()> Test_Case = [&]() {
        int n; cin >> n;
        int ar[n];
        for(int i = 0; i < n; i++) {
            cin >> ar[i];
        }
        int64_t mx = 0, sum = 0;
        sort(ar, ar + n, greater<int>());
        int i = 0, j = n - 1;
        for(int i = 0; i < n; i++) {
            if(i > 1) {
                if((i & 1) == 0) {
                    if(sum + ar[i] < sum) {
                        break;
                    }
                    else {
                        sum += ar[i];
                    }
                }
                else {
                    if(sum - ar[i] > sum) {
                        break;
                    }
                    sum -= ar[i];
                }
            }
            else {
                if(i & 1) sum = sum - ar[i];
                else sum = sum + ar[i];
            }
        }
        cout << sum << '\n';
    };

    int32_t Case = 1;    cin >> Case;
    for (int T = 1; T <= Case; T++) {
        Test_Case();
    }
    return 0;
}