#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
void dfs(vector<set<ll>>& adj,vector<bool>& vis,ll s,ll& ans,vector<ll>& comp,vector<ll>& p){
  if(vis[s])return;
  vis[s]=true;
  for(auto u:adj[s]){
    if(!vis[u]){
      comp[p[u-1]]=ans;
      dfs(adj,vis,u,ans,comp,p);
    }
  }
  
}
void dfs2(vector<vector<ll>>& adj,ll s,ll p,vector<ll>& tin,vector<ll>& tout,ll& ti,vector<vector<ll>>& succ,vector<ll>& dist){
  tin[s]=(++ti);
  for(auto u:adj[s]){
    if(u!=p){
      succ[u][0]=s;
      dist[u]=dist[s]+1;
      dfs2(adj,u,s,tin,tout,ti,succ,dist);
    }
  }
  tout[s]=(++ti);
}
bool is_anc(ll a,ll b,vector<ll>&tin, vector<ll>& tout){
  return (tin[a]<=tin[b] && tout[a]>=tout[b]);
}
ll lca(ll a,ll b,vector<vector<ll>>& succ,vector<ll>& tin,vector<ll>& tout){
  if(is_anc(a,b,tin,tout))return a;
  if(is_anc(b,a,tin,tout))return b;
  ll n=tin.size()-1;
  ll k=ceil(log2(n));
  for (ll i = k; i >= 0; i--) {
        if (!is_anc(succ[a][i], b,tin,tout))
            a = succ[a][i];
    }
  return succ[a][0];
}
void bfs(vector<vector<ll>>& adj,vector<bool>& vis,vector<ll>& dist,queue<ll>& q,ll x){
  dist[x]=0;
  q.push(x);
  vis[x]=true;
  while(q.size()!=0){
    ll s=q.front();
    q.pop();
    for(auto u:adj[s]){
      if(vis[u])continue;
      vis[u]=true;
      dist[u]=dist[s]+1;
      q.push(u);
    }
  }
}
ll find(ll x,vector<ll>& link){
  while(x!=link[x])x=link[x];
  return x;
}
void unite(ll a,ll b,vector<ll>& link,vector<ll>& size){
  a=find(a,link);
  b=find(b,link);
  if(size[a]<size[b])swap(a,b);
  size[a]+=size[b];
  link[b]=a;
}
ll modinv(ll A, ll M){
    ll m0 = M;
    ll y = 0, x = 1;
    if (M == 1)
        return 0;
    while (A > 1) {
        ll q = A / M;
        ll t = M;
        M = A % M, A = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0)
        x += m0;
    return x;
}
ll power(ll x,ll y,ll p){
  ll res=1;
  x%=p;
  if(x==0)return 0;
  while(y>0){
    if(y%2==1){
      res=(res*x)%p;
    }
    y/=2;
    x=(x*x)%p;
  }
  return res;
}
ll mpf(ll x, vector<ll>& primes){
  for(auto p:primes){
        if(p*p>x)break;
        while(x%p==0)x/=p;
        if(x==1)return p;
    }
  return x;
}
int main() 
{
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  ll N = pow(10,5);
  vector<bool> prime(N + 1, true);
  for (int p = 2; p * p <= N; p++) {
      if (prime[p] == true) {
          for (int i = p * p; i <= N; i += p)
              prime[i] = false;
      }
  }
  vector<ll> primes;
  for(ll i=2;i<=N;i++){
    if(prime[i])primes.pb(i);
  }
  ll t;
  cin>>t;
  //t=1;//use this when no testacses
  ll mod=pow(10,9)+7;
  while(t--){
    //Author:Aryan Prakash
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll& x:a)cin>>x;
    sort(a.begin(),a.end());
    ll i=n-3;
    ll ans=a[n-1]-a[n-2];
    while(i>=1){
      if(a[i]>=0 && a[i-1]>=0)ans+=(a[i]-a[i-1]);
      i-=2;
    }
    if(n%2==1 && a[0]>=0)ans+=a[0];
    cout<<ans<<endl;
  }
}