#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int long long
const int MOD = 1000000007;
#define sz(x) (ll)(x).size()
#define rd ({ll x; cin >> x; x; })
#define dbg(x) cerr << "[" #x "]  " << (x) << "\n"
// #define errv(x) {cerr << "["#x"]  ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
// #define cerr if(0)cerr
#define xx first
#define yy second
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
/*_________________________________________________________________________________________________________________________*/

void Solve()
{
    ll n;
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    sort(arr.rbegin(), arr.rend());
    vector<ll> sums;
    ll ans = 0, mx = 0;
    for (int i = 0; i < n; i++) {
        if (i & 1)
            ans -= arr[i];
        else
            ans += arr[i];
        sums.push_back(ans);
    }
    if (n == 1) {
        mx = max(mx, arr[0]);
        cout << mx << "\n";
        return;
    }
    ll mn = sums[0], mx2 = sums[1];
    for (ll i = 0; i < n; i++) {
        if (i % 2 == 0)
            mn = min(mn, sums[i]);
        else
            mx2 = max(mx2, sums[i]);
        mx = max(mx, min(mn, mx2));
    }
    cout << mx << "\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Case #" << i << ": "; // cout << "Case " << i << ": ";
        Solve();
    }
    return 0;
}
// Coded by Tahsin Arafat (@TahsinArafat)