#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define endl '\n'
#define ll long long
#define ld long double
#define vi vector<ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define srt(v) sort(v.begin(),v.end())
#define rsrt(v) sort(v.rbegin(),v.rend())
#define rep(i, a, b) for(ll i = (a); i < (b); i++)
#define trace(x) cout<<#x<<": "<<x<<endl;
#define print(v) for(auto e:v) cout<<e<<" "; cout<<endl;
#define printp(v) for(auto e:v) cout<<e.first<<" "<<e.second<<endl;
const int N=5e5+10;
void solve(){
    ll n;cin>>n;
    vi p(n);
    rep(i,0,n){
        cin>>p[i];
    }
    rsrt(p);
    ll sum = 0;
    ll one=0,two=0;
    for(int i = 0;i<n;i++){
        if(one>0 && two>0){
            if(i&1){
                ll ki = sum ;
                if(ki-p[i]<sum){
                    sum -= p[i];
                }
                else{
                    break;
                }
            }
            else{
                ll ki = sum;
                if(ki+p[i]>sum){
                    sum+=p[i];
                }
                else{
                    break;
                }
            }
        }
        else{
            if(i&1){
                sum -=p[i];
                two++;
            }
            else{
                sum += p[i];
                one++;
            }
            
        }
    }
    cout<<sum<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;cin>>t;
    for(int i =1;i<=t;i++){
        solve();
    }
    return 0;
}