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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) 
            cin >> a[i];

        sort(a.begin(), a.end(), greater<int>());

        long long S = 0;
        bool royPlayed = false, hrPlayed = false;
        bool royTurn = true;
        int idx = 0;

        while (idx < n) {
            int x = a[idx];

            if (royTurn) {
                if (!royPlayed || x > 0) {
                    S += x;
                    royPlayed = true;
                    idx++;
                } else {
                    break;
                }
            } else {
                if (!hrPlayed || x > 0) {
                    S -= x;
                    hrPlayed = true;
                    idx++;
                } else {
                    // stop
                    break;
                }
            }

            royTurn = !royTurn;
        }

        cout << S << "\n";
    }
    return 0;
}