#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define fr first
#define sc second
#define abs(Value) ((Value>=0)?(Value):(-Value))
inline int read(){
	int res=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
	return res*f;
}
const int N=35;
const double Delta=0.996,Eps=1e-3;
int Qr,n,a[N],b[N],c;
void swaps(int &c,int xa,int xb){
	c-=2*(a[xa]-b[xb]);
	swap(a[xa],b[xb]);
}
int solve(){
	int sa=(n>>1),sb=n-sa,ans=abs(c);
	double T=1e5;
	while (T>Eps){
		int lc=c,xa=rand()%sa+1,xb=rand()%sb+1;
//		cout<<xa<<' '<<xb<<'\n';
		swaps(c,xa,xb),ans=min(ans,abs(c));
		if ((double)abs(lc)-(double)abs(c)>Eps&&exp((double)abs(lc)-(double)abs(c)/T)<=(double)rand()/(double)RAND_MAX)
			swaps(c,xa,xb);
		T*=Delta;
	}
	return ans;
}
signed main(){
	srand(time(0));
	Qr=read();
	while (Qr--){
		n=read();
		if (n==1){
			int x=read();
			cout<<x<<'\n';
			continue;
		}
		c=0;
		for (int i=1;i<=(n>>1);i++) a[i]=read(),c+=a[i];
		for (int i=1;i<=n-(n>>1);i++) b[i]=read(),c-=b[i];
		int res=1e18;
		double timer=clock();
		while (clock()-timer<=CLOCKS_PER_SEC*0.05) res=min(res,solve());
		cout<<res<<'\n';
	}
	return 0;
}

70 分