#include <bits/stdc++.h>
#define nl '\n'
#define ll long long
#define all(c) c.begin(),c.end()
#define print(c) for(auto e : c) cout << e << " "; cout << nl
using namespace std;
void solve()
{
    int n; cin >> n;
    vector<int> a(n);
    for(auto &e : a) cin >> e;
    sort(all(a)); reverse(all(a));

    multiset<int> neg, posForHridoy;
    for(auto e : a)
    {
        if(e >= 0) posForHridoy.insert(e);
        else neg.insert(e);
    }

    // cout << neg.size() << " " << posForHridoy.size() << nl; // ok

    ll curr_sum = 0;
    ll mx_at_any_point = -1E18, mn_at_any_point = 1E18;

    for (int i = 0; i < n; i++)
    {
        if(i%2 == 0) // roy's turn
        {
            curr_sum += a[i];

            auto it = posForHridoy.find(a[i]);

            if(it != posForHridoy.end()) posForHridoy.erase(it);
            else 
            {
                it = neg.find(a[i]);
                neg.erase(it);
            }
        }
        else
        {
            if(!posForHridoy.empty())
            {
                auto it = posForHridoy.begin();
                curr_sum -= *it;
                --posForHridoy.begin();
            }
            else 
            {
                auto it = --neg.end();
                curr_sum -= *it;
                --neg.end();
            }
        }

        if((i & 1)) mn_at_any_point = min(mn_at_any_point, curr_sum);
        else mx_at_any_point = max(mx_at_any_point, curr_sum);

        // cout << i << ": " << mn_at_any_point << ", " << mx_at_any_point << nl;

        if(i >= 1)
        {
            if(mn_at_any_point != mx_at_any_point)
            {
                if(i & 1) cout << mn_at_any_point << nl; 
                else cout << mx_at_any_point << nl; 
                return;
            }
        }
    }
    
    cout << mx_at_any_point << nl;
    // cout << mx_at_any_point << " -- " << mn_at_any_point << nl;
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int t; cin >> t;
    for(int tt = 1; tt <= t; tt++)
    {
        // cout << "TEST CASE-" << tt << nl;
        solve();
    }

    return 0;
}