#include<bits/stdc++.h>
using namespace std;
#define int long long int

int find_max_freq(vector<int> cnt) {
    int max_f = 0;
    for (int count : cnt) {
        if (count > max_f) {
            max_f = count;
        }
    }
    return max_f;
}

int solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    vector<int> scores(n + 1, 0);
    for (int k = 1; k <= n; ++k) {
        if (k % 2 != 0) {
            scores[k] = scores[k - 1] + a[k - 1];
        } else {
            scores[k] = scores[k - 1] - a[k - 1];
        }
    }

    int V = scores[n];
    for (int k = n - 1; k >= 2; --k) {
        if (k % 2 == 0) {
            V = max(scores[k], V);
        } else {
            V = min(scores[k], V);
        }
    }

    cout << V << endl;
    return 0;
}
int32_t main(){
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
 
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif
    

    int t;
    t = 1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}