RT

#include<bits/stdc++.h>
#define down 0.995
using namespace std;
int n;
int a[100005];
int fir[10005],sec[10005],p,q,now1[10005],now2[10005];
int ans=INT_MAX;
long long check(){
	long long cnt=0;
	for(int i=1;i<=p;i++){
		cnt+=now1[i];
	}
	for(int i=1;i<=q;i++){
		cnt-=now2[i];
	}
	return cnt>0?cnt:-cnt;
}
void sa(){
	double t=10000;
	while(t>1e-12){
		for(int i=1;i<=p;i++){
			now1[i]=fir[i];
		}
		for(int i=1;i<=q;i++){
			now2[i]=sec[i];
		}
		swap(now1[rand()%p+1],now2[rand()%q+1]);
		int cnt=check();
		double f=cnt-ans;
		if(f<0){
			for(int i=1;i<=p;i++){
				fir[i]=now1[i];
			}
			for(int i=1;i<=q;i++){
				sec[i]=now2[i];
			}
			ans=cnt;
		}
		else if(exp(-f/t)*RAND_MAX>rand()){
			for(int i=1;i<=p;i++){
				fir[i]=now1[i];
			}
			for(int i=1;i<=q;i++){
				sec[i]=now2[i];
			}
		}
		t*=down;
	}
}
int main(){
	srand(time(NULL));
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		ans=INT_MAX;
		q=0;
		p=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=n/2;i++){
			fir[++p]=a[i];
		}
		for(int i=n/2+1;i<=n;i++){
			sec[++q]=a[i];
		}
		for(int i=1;i<=40;i++)sa();
		cout<<ans<<endl;
	}
	return 0;
}