#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc; cin >> tc;

    test:
    while (tc--) {
        ll n; cin >> n;
        
        ll arr[n];
        for (auto &u : arr) cin >> u;
        sort(arr, arr+n);
        reverse(arr, arr+n);

        if (n == 2) {
            cout << arr[0] - arr[1] << "\n";
            goto test;
        }
        
        ll temp = arr[0]-arr[1];
        for (ll i = 2; i < n; i++) {
            if (i & 1) {
                if (temp - arr[i] > temp) break;
                else temp -= arr[i];
            }
            else {
                if (temp + arr[i] < temp) break;
                else temp += arr[i];
            }
        }

        cout << temp << "\n";
        
    }
}