/*
 * Name : Md. Fahmidur Rahman Nafi
 * Date : 2025-07-14   Time : 21:45:33
 */

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ld long double
#define ull unsigned long long
#define lcm(a,b) ((a*b)/__gcd(a,b))
#define debug(x) cout << "Debug : " << x << endl;
const double PI = 2 * acos(0.0);
const int MOD = 1000000007;

void solve(){
    int x;
    cin >> x;
    vector <int> a(x); 
    deque <int> p, n;
    for (auto &i : a) cin >> i, i >= 0 ? p.push_back(i) : n.push_back(i);
    
    ll cnt = 0;    
    sort(p.begin(), p.end());
    sort(n.rbegin(), n.rend());
    ll ans = -1;
    for (int i = 1; i <= x; i++){
        if (!p.empty()){
            if (i % 2 != 0){    // kmns --> maximize
                cnt += p.back();
                p.pop_back();
            }
            else{
                cnt -= p.back();
                p.pop_back();
            }
        }
        else{
            if (i % 2 != 0){
                if (i != 1){
                    break;
                }
                else{
                    cnt += n.front();
                    n.pop_front();
                }
            }
            else{
                if (i != 2){
                    break;
                }
                else{
                    cnt += (-n.front());
                    n.pop_front();
                }
            }
        }

        // debug(cnt);
    }

    cout << cnt << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    while(t--){
        solve();
    }
}