#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{
    long long ans1 = 0; // max
    long long ans2 = 1e18; // min
    int i = n-3;
    int turn = 0;
    long long score = a[n-1] - a[n-2];
    ans1 = max(ans1,score);
    while(i >= -1){
      if(turn == 0){
        ans1 = max(ans1,score);
        if(i >= 0) score += a[i];
      }
      else{
        ans2 = min(ans2,score);
        if(i >= 0) score -= a[i];
      }
      turn ^= 1;
      i--;
    }
    cout << min(ans1,ans2) << endl;
  }
  
  
  
}
 
 
 
 
int main()
{
    int t = 1;
    cin >> t;
    
    while(t--) solve();
    return 0;
}