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

int main() {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n; 
        deque<ll> dq;
        for(int i = 0; i < n; i++) {
            ll x; cin >> x;
            dq.push_back(x);
        }

        sort(dq.begin(), dq.end());

        ll ans = 0;
        ll cnt = 2;

        ll first = dq.back(); dq.pop_back();
        ll second = dq.back(); dq.pop_back();

        ans = first - second;
       // cerr << ans << endl;
        pair<ll, ll> max_pair = {ans, cnt};
        pair<ll, ll> min_pair = {ans, cnt};
       // cerr << max_pair.first << endl;

        cnt += 1;

        while(!dq.empty()) {
  			//cerr << dq.back() << endl;
            ans += dq.back();
           // cerr << ans << endl;
            dq.pop_back();

            if(ans > max_pair.first) {
                max_pair = {ans, cnt};
            }

            cnt++;

            if(!dq.empty()) {
                ans -= dq.back();
                dq.pop_back();

                if(ans < min_pair.first) {
                    min_pair = {ans, cnt};
                }
                cnt++;
            }
        }

        if(max_pair.second - 1 <= min_pair.second) {
            cout << max_pair.first << endl;
        } else {
            cout << min_pair.first << endl;
        }
    }
}