#include <bits/stdc++.h>
#define ll long long
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>());
        ll S = 0;

        vector<ll> dp(N+1, 0);
        dp[N]=0;
        for(int i=N-1;i>=2;i--) {
            dp[i]=0;
            if (i%2==0) {
                dp[i]=max(dp[i],dp[i+1]+A[i]); // roy
            } else {
                dp[i]=min(dp[i],dp[i+1]-A[i]); // hridoy
            }
        }
        cout << A[0]-A[1]+dp[2] << endl;
    }
    return 0;
}