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

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int a[n];

        for(int i=0;i<n;i++)
        {
            cin >> a[i];
        }

        long long int s=0;

        sort(a,a+n);
        int b[n];

        for(int i=0;i<n;i++)
        {
            b[i]= a[n-(i+1)];
        }

        s = b[0] - b[1];

        long long p[n]; 
        p[0] = b[0];
        p[1] = p[0] - b[1];
        for(int i=2; i<n; i++)
        {
            if(i%2==0)
            {
                p[i] = p[i-1] + b[i];
            } 
            else
            {
                p[i] = p[i-1] - b[i];
            } 
        }
        s = p[n-1];
        for(int i=n-2; i>=1; i--) 
        {
            if(i%2==0)
            {
                s = min(p[i], s);
            } 
                
            else
            {
                s = max(p[i], s);
            }       
                
        }
        cout << s << endl;
    }
    return 0;
}