$rt$

#include<bits/stdc++.h>
#define ll long long
#define down 0.996
#define S 19260817
using namespace std;
const int N=1e5+5;
ll T,n;
ll arr[N];
double sum1,sum2;
double ans,fans;

void sa() {
	double t=3000;
	while(t>1e-15) {
		ll x=rand()%(n>>1)+1;
		ll y=(n>>1)+rand()%(n+1>>1)+1;
		sum1=sum1-arr[x]+arr[y];
		sum2=sum2-arr[y]+arr[x];
		swap(arr[x],arr[y]);
		ll w=abs(sum1-sum2);
		ll dw=w-ans;
		if(dw<0) {
			ans=w;
			fans=min(ans,fans);
		}
		else if(exp(-dw/t)*RAND_MAX>rand()) ans=w;
		else {
			swap(arr[x],arr[y]);
			sum1=sum1-arr[x]+arr[y];
			sum2=sum2-arr[y]+arr[x];
		}
		t*=down;
	}
}

void ee() {
	for(int i=1;i<=1000;i++) {
		sa();
	}
}

void work() {
	sum1=sum2=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>arr[i];
	if(n==0) {
		cout<<0<<endl;
		return ;
	}
	if(n==1) {
		cout<<arr[1]<<endl;
		return ;
	}
	for(int i=1;i<=n>>1;i++) {
		sum1+=arr[i];
	}
	for(int i=(n>>1)+1;i<=n;i++) {
		sum2+=arr[i];
	}
	fans=ans=abs(sum1-sum2);
	ee();
	cout<<fans<<endl;
}

int main() {
	cin>>T;
	while(T--) {
		work();
	}
 	return 0;
}