#include <bits/stdc++.h>
using namespace std;
 
 
const int MOD = 1e9 + 7;
const int MX = 1e6 + 10;
long long dp[MX + 100][2];
 
 
void solve(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int &i : a) cin >> i;
  sort(a.begin(),a.end());
  if(a[n-2] < 0){
    cout << a[n-1] - a[n-2] << endl;
    return;
  }
  else{
    vector<int> dp(n+1);
    for(int i = 1; i <= n ; i++){
      int t = n - i;
      if(t % 2 == 0){
        dp[i] = max(dp[i],dp[i-1] + a[i-1]);
      }
      else{
        dp[i] = min(dp[i],dp[i-1] - a[i-1]);
      }
    }
    cout << dp[n] << endl;
  }
  
  
  
}
 
 
 
 
int main()
{
    int t = 1;
    cin >> t;
    
    while(t--) solve();
    return 0;
}