#include<bits/stdc++.h>
#define endl '\n'
#define test() puts("************");
using namespace std;
const int N=31;
int T,v[N],n,ans=INT_MAX,all;
inline double rd(){
    return rand()*1.0/RAND_MAX;
}
inline int calc(){
	int cnt=0;
	for(int i=1;i<=(n+1)>>1;i++) cnt+=v[i];
	return abs(all-(cnt<<1));
}
void SA(){
    double T = 5000;
    int org = calc();
    ans = min(ans, org);
    while(T > 1e-10){
        int x = rd()*(n-(n+1)/2)+(n+1)/2;
        int y = rd()*((n+1)/2-1)+1;
        //cout<<x<<" "<<y<<endl;
        swap(v[x], v[y]);
        int now = calc();
        int delta = now - org;
        if(delta < 0){
            org = now;
            ans = min(ans, now);
        } else {
            if(exp(-delta *1.0/ T) > rd()){
                org = now;
            } else {
                swap(v[x], v[y]);
            }
        }
        T *= 0.9112;
    }
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>T;
    double t=0.97/T;
    for(int x=1;x<=T;x++){
    	cin>>n;
    	all=0;
    	for(int i=1;i<=n;i++) cin>>v[i],all+=v[i];
    	if(n==1){
    		cout<<v[1]<<endl;
    		continue;
		}
		if(n==2){
			cout<<abs(v[1]-v[2])<<endl;
			continue;
		}
		ans=INT_MAX;
    	while(clock()<CLOCKS_PER_SEC*t*x) SA();
    	cout<<ans<<endl;
    	//test();
	}
	return 0;
}

WA 0pts,是SA打错了还是参数有问题