/* GREEN UNIVERSITY OF BANGLADESH
    Md DinIslam, Batch-221 (CSE)
*/
#include <bits/stdc++.h>
using namespace std;

// Debug..
#ifdef LOCAL
#include "debug.h"
#else
#define dg(x...)
#endif

#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(x) int(x.size())
#define arr array

void Din() {
    int n;
    cin >> n;

    vector<int> v(n);
    for (auto &x : v) {
        cin >> x;
    }

    sort(all(v), greater());

    ll ans = 0, curr_sum = 0;
    int turn = 0;

    for (int i = 0; i < n; ++i) {
        turn += 1;
        if (i & 1 ^ 1) {
            // if (curr_sum + v[i] < curr_sum && turn > 1) {
            //     break;
            // }
            curr_sum += v[i];
            if (turn > 1)
                ans = max(ans, curr_sum);
        }
        else {
            if (curr_sum - v[i] > curr_sum && turn > 1)
                break;
            curr_sum -= v[i];
            if (turn > 1)
                ans = max(ans, curr_sum);
        }
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        // cout << "Case " << i << ": ";
        Din();
    }
    return 0;
}