#include <vector>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define A(a) begin(a),end(a)
#define pb push_back
#define pp partition_point
#define K first
#define V second
#define krep(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int) (size(x))

template <typename T>
std::istream& operator >>(std::istream& input, std::pair <T, T> & data)
{
    input >> data.first >> data.second;
    return input;
}
template <typename T>
std::istream& operator >>(std::istream& input, std::vector<T>& data)
{
    for (T& x : data)
        input >> x;
    return input;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const pair <T, T> & data)
{
    output << "(" << data.first << "," << data.second << ")";
    return output;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const std::vector<T>& data)
{
    for (const T& x : data)
        output << x << " ";
    return output;
}
struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vll =  vector<ll>;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? (a = b, 1) : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? (a = b, 1) : 0; }
inline long long Bit(long long mask, long long bit) { return (mask >> bit) & 1; }


constexpr ll NN = 2e5, M = 1000000007, L = 20;
const ll oo = 1e15;
void run()
{
    ll n; cin >> n;
    vll a(n); cin >> a;
    ranges::sort(a),ranges::reverse(a);
    if(n%2 == 0){
        n++;
        a.pb(0);
    }
    auto p = a;
    for(int i=1;i<n;i++){
        if(i%2)p[i]=-p[i];
        p[i]+=p[i-1];
    }
    /*
        roy can achieve a value only if they get to that sum on his turn
        i.e his oponent just subtracted something
        AND it should be the case that
        its never below that sum on his oponents turn
    */
   ll ans = p[1];
   ll opmn = oo;
   for(int i = 2;i<n;i+=2){
        ll x = p[i-1];
        if(x <= opmn) ckmax(ans,x);
        ckmin(opmn,p[i]);
   }

   cout << ans << '\n';
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    //nick belov always reads the entire problem statement.
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int t; cin>>t; while(t--) run();
}