#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<long long> A(N);
        for (int i = 0; i < N; i++) cin >> A[i];
        sort(A.rbegin(), A.rend());

        vector<vector<vector<vector<long long>>>> dp(
            N + 1, vector<vector<vector<long long>>>(
                2, vector<vector<long long>>(
                    2, vector<long long>(
                        2, LLONG_MIN))));

        for (int t = 0; t <= 1; t++)
            for (int mr = 0; mr <= 1; mr++)
                for (int mh = 0; mh <= 1; mh++)
                    dp[N][t][mr][mh] = 0;

        for (int i = N - 1; i >= 0; i--) {
            for (int t = 0; t <= 1; t++) {
                for (int mr = 0; mr <= 1; mr++) {
                    for (int mh = 0; mh <= 1; mh++) {
                        long long stop_val = LLONG_MIN;
                        if (mr && mh) stop_val = 0;

                        if (t == 0) {
                            long long pick_val = A[i] + dp[i + 1][1][1][mh];
                            dp[i][t][mr][mh] = max(stop_val, pick_val);
                        } else {
                            long long pick_val = -A[i] + dp[i + 1][0][mr][1];
                            if (stop_val == LLONG_MIN)
                                dp[i][t][mr][mh] = pick_val;
                            else
                                dp[i][t][mr][mh] = min(stop_val, pick_val);
                        }
                    }
                }
            }
        }

        cout << dp[0][0][0][0] << "\n";
    }
    return 0;
}