#include<bits/stdc++.h>
using namespace std;
#define Faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define test_case int t;cin>>t;while(t--)


int main(){


        Faster;

        test_case{

        ll i,n;

        cin>>n;

        vector<ll> v(n);

        for(i=0; i<n; i++)cin>>v[i];

        sort(v.rbegin(),v.rend());

        ll sum=v[0]-v[1];

        for(i=2; i<n; i++){
          if(v[i]<0){
            break;
          }
          if(i%2==0){
            sum+=v[i];
          }
          else sum-=v[i];
        }

        cout<<sum<<endl;

      }

        
}