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

#define ll long long
#define int long long
#define all(x) (x).begin(), (x).end()
#define f(i, n) for (int i = 0; i < n; i++)
#define trace(x) cerr << #x << ": " << x << '\n'
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> v(n);
        f(i, n) cin >> v[i];
        sort(all(v));
        reverse(all(v));
        int r = -1e18, c = 1e18, s = 0, res = 1e18;
        f(i, n)
        {
            if (i & 1)
                s = min(s, s - v[i]);
            else
                s = max(s, s + v[i]), r = max(r, s);
            if (i > 0)
            {
                if (i & 1)
                    c = min(c, s);
                res = min({res, r, c});
            }
            // cout << s << ' ' << c << ' ' << r << ' ' << res << endl;
        }
        cout << res << endl;
    }
}