mo ni tui huo da ma ru xia:

#include<bits/stdc++.h>
using namespace std;
int t,n,a[40];
int func(){
	int mid=(n+1)>>1,sum1=0,sum2=0;
	for(int i=1;i<=mid;i++) sum1+=a[i];
	for(int i=mid+1;i<=n;i++) sum2+=a[i];
	return abs(sum1-sum2);
}
int solve(){
	double T=1e5,eps=1e-8,delta=0.98;
	int now=func(),ans=now;
	while(T>eps){
		int x=rand()%((n+1)>>1)+1,y=rand()%((n+1)>>1)+((n+1)>>1);
		swap(a[x],a[y]);
		int now=func(),d=now-ans;
		if(d<0) ans=now;
		else if(exp(d/T)<rand()) swap(a[x],a[y]);
		T*=delta;
	}
	return ans;
}
int main(){
	srand(time(0));
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		printf("%d\n",solve());
	}
	return 0;
}