#include<bits/stdc++.h>
using namespace std;
long long solve(vector<long long>& v){
  if(v.size()==1)return v[0];
  if(v.size()==2)return v[1]-v[0];
  if(v.size()==3)return max(v[1],v[2]-v[1]+v[0]);
  auto x=v.back();
  v.pop_back();
  return x-solve(v);
}
int N;
int main(){
  int T;
  cin>>T;
while(T--){
  cin>>N;
  vector<long long> v(N);
  for(auto& x:v)cin>>x;
  sort(v.begin(),v.end());
  cout<<solve(v)<<'\n';
}}