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

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

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

        int ans = 0;
        int cnt = 2;

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

        ans = first - second;
        cerr << ans << endl;
        pair<int, int> max_pair = {ans, cnt};
        pair<int, int> 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;
        }
    }
}