/**
*    In the name of Allah
*    We are nothing and you're everything
*    Ya Muhammad!
**/
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ull = uint64_t;
 
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define int long long
 
const char nl = '\n';
const int N = 1e5+5;
const ll inf = 0x3f3f3f3f3f3f3f3fll;

void solve() {
	int n; cin >> n;
	vector<int> a(n);
	for (auto &i: a)cin >> i;
	
	sort(all(a));
	int sum = a.back();
	a.pop_back();
	sum = sum-a.back();
	a.pop_back();
	n = sz(a);
	int turn = 0;
	for (int i = n-1; i >= 0; --i) {
		if (a[i] < 0)break;
		if (turn == 0)sum += a.back();
		else sum -= a.back();
		a.pop_back();
		turn = 1-turn;
	}
	
	cout << sum << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while(t--)solve();
  return 0;
}