#include<bits/stdc++.h>
using namespace std;
#define int             long long
#define pb              push_back
#define endl            '\n'
#define debug           cout<<"HERE"<<endl;
#define ff              first
#define ss              second
void edm()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}
void solve()
{
    int n;cin>>n;
    int arr[n];
    int pos=0;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        if(arr[i]>0)pos++;
    }
    int ans=0;
    sort(arr,arr+n);
    if(pos==0)
    {
        ans = ans + arr[n-1];
        ans = ans - arr[n-2];
        cout<<ans<<endl;
        return;   
    }
    int now=1;
    ans = ans + arr[n-1];
    ans = ans - arr[n-2];
    for(int i=n-3;i>=0;i--)
    {
        if(arr[i]<=0)break;
        if(now)
        {
            ans = ans + arr[i];
            now=0;
        }
        else
        {
            ans = ans - arr[i];
            now=1;
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    //edm();
    int t = 1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        ///cout<<"Case "<<i<<": ";
        solve();
    }
}