#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<long long>>> curr(2, vector<vector<long long>>(2, vector<long long>(2)));
        vector<vector<vector<long long>>> next(2, vector<vector<long long>>(2, vector<long long>(2, 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 = (mr && mh) ? 0 : LLONG_MIN;
                        if (t == 0) {
                            long long pick_val = A[i] + next[1][1][mh];
                            curr[t][mr][mh] = max(stop_val, pick_val);
                        } else {
                            long long pick_val = -A[i] + next[0][mr][1];
                            if (stop_val == LLONG_MIN)
                                curr[t][mr][mh] = pick_val;
                            else
                                curr[t][mr][mh] = min(stop_val, pick_val);
                        }
                    }
                }
            }
            swap(curr, next);
        }

        cout << next[0][0][0] << "\n";
    }

    return 0;
}