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

#define int long long

const long double PI = 3.14159265359;

void solve()
{
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    int sum = 0;

    int parity[] = {n / 2, (n + 1) / 2};
    // magn, sign, even - odd position
    vector<array<int, 3>> vals;
    for (int i = 1; i <= n; i++)
    {
        vals.push_back({abs(arr[i]), arr[i] < 0, i % 2});
    }

    sort(vals.rbegin(), vals.rend());

    for (int i = 0; i < vals.size(); i++)
    {
        if (vals[i][1] == 0)
        {
            // pos
            if (parity[vals[i][2]])
                sum += vals[i][0], parity[vals[i][2]]--;
            else
                sum -= vals[i][0], parity[!vals[i][2]]--;
        }
        else
        {
            // neg
            if (parity[!vals[i][2]])
                sum += vals[i][0], parity[!vals[i][2]]--;
            else
                sum -= vals[i][0], parity[vals[i][2]]--;
        }
    }
    cout << sum << '\n';
}

signed main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("input.txt", "r"))
    {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}