#if __has_include("../stdc++.h")
	#include "../stdc++.h"
#else
	#include <bits/stdc++.h>
#endif

template <typename T>
std::istream &operator>>(std::istream &in, std::vector<T> &v)
{
    for (T &x : v)
        in >> x;
    return in;
}

template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v)
{
    for (std::size_t i = 0; i < v.size(); ++i)
        out << v[i] << (i + 1 == v.size() ? "" : " ");
    return out;
}

inline void yes() { std::cout << "Yes\n"; }
inline void no()  { std::cout << "No\n";  }

using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<long long> a(n);
    cin >> a;
    sort(a.begin(), a.end(), greater<long long>());
    long long curr = 0;
    curr += a[0];
    curr -= a[1];
    long long bestR = curr;
    long long bestH = curr;
    if (n == 2) {
        cout << curr << '\n';
        return;
    }
    for (int i = 2; i < n; i++) {
        if (i % 2 == 0) {
            if (curr > bestR && i != 2) {
                cout << bestR << '\n';
                return;
            }
            if (curr < bestR && i != 2) {
                cout << bestR << '\n';
                return;
            }
            if (curr + a[i] < bestR) {
                cout << bestR << '\n';
                return;
            }
            bestR = max(bestR, curr);
            // cerr << "bestR: " << bestR << '\n';
            curr += a[i];
            if (i == n - 1) {
                bestR = max(bestR, curr);
            }

        } else {
            bestH = min(bestH, curr);
            // cerr << "bestH: " << bestH << '\n';
            curr -= a[i];
            if (i == n - 1) {
                bestH = min(bestH, curr);
            }
        }
    }
    cout << max(bestH, bestR) << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}