#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::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        sort(a.rbegin(), a.rend());
        vector<int> p(n + 1, 0), dp1(n + 1), dp2(n + 1);
        for (int i = 0; i < n; ++i)
            p[i + 1] = p[i] + ((i & 1) ? -a[i] : a[i]);
        dp1[n] = dp2[n] = p[n];
        for (int k = n - 1; k >= 0; k--)
        {
            if ((k & 1) == 0)
            {
                dp1[k] = max(p[k], dp2[k + 1]);
                dp2[k] = dp2[k + 1];
            }
            else
            {
                dp2[k] = min(p[k], dp1[k + 1]);
                dp1[k] = dp1[k + 1];
            }
        }
        cout << dp1[0] << '\n';
    }
    return 0;
}