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


int main() {

    long long t;
    cin>>t;

    while(t--)
    {
        long long n;
        cin>>n;
        long long a[n];
        for(long long i=0;i<n;i++) cin>>a[i];
        sort(a,a+n);
        long long ans=(a[n-1]-a[n-2]);
        long long T=0;
        for(long long i=n-3;i>=0;i--)
        {
            if(T==0)
            {
                if(ans+a[i]>ans)
                {
                    ans+=a[i];
                    T^=1;
                }
                else break;
            }
            else
            {
                if(ans-a[i]<ans)
                {
                    ans-=a[i];
                    T^=1;
                }
                else break;
            }
        }
        cout<<ans<<"\n";
    }
    
    return 0;
}