#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--){
    ll n, a, S = 0;
    cin >> n;
    vector<int> P, N;
    for (int i = 0; i < n; i++){
      cin >> a;
      if (a > 0) P.push_back(a);
      else N.push_back(a);
    }
    sort(P.begin(), P.end());
    sort(N.begin(), N.end());
    if (P.size()){
      S += P.back();
      P.pop_back();
    } else if (N.size()){
      S += N.back();
      N.pop_back();
    }
    if (P.size()){
      S -= P.back();
      P.pop_back();
    } else if (N.size()){
      S -= N.back();
      N.pop_back();
    }
    ll cur = S;
    if (P.size()){
      S += P.back();
      P.pop_back();
    }
    if (cur >= S){
      cout << cur << endl;
      continue;
    }
    cur = S;
    ll mn = S;
    int last = 0;
    while (true){
      int f = 1;
      last = 0;
      if (P.size()){
        S -= P.back();
        P.pop_back();
        f = 0;
        cur = S;
      } 
      if (f) break;
      f = 1;
      if (P.size()){
        S += P.back();
        P.pop_back();
        f = 0;
        last = 1;
        mn = min(mn, S);
      }
      if (f or P.empty()) break;
    }
    if (!last) mn = min(mn, cur);
    cout << mn << endl;
  }
}