#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<cmath>#include<iostream>#include<utility>#include<vector>#include<queue>#include<map>#include<algorithm>#include<set>#include<sstream>#include<stack>#define ii long long int#define pi 2*acos(0.0)#define eps 1e-7#define mem(x,y) memset(x,y,sizeof(x))#define all(x) x.begin(), x.end()#define pb push_back#define sz(a) a.size()using namespace std;int a[40],n1,n,SUM;vector <int> v1,v2;void call1(int i){ if (i>n1) { v1.pb(SUM); return; } call1(i+1); SUM+= a[i]; call1(i+1); SUM-= a[i];}void call2(int i){ if (i>n) { v2.pb(SUM); return; } call2(i+1); SUM+= a[i]; call2(i+1); SUM-= a[i];}int main(){ int t; scanf("%d",&t); while (t--) { v1.clear(); v2.clear(); int sum= 0,mid; cin >> n; for (int i=1; i<=n; ++i) cin >>a[i],sum+= a[i]; mid= sum/2; n1= n/2; SUM= 0; call1(1); int sz= sz(v1); SUM= 0; call2(n1+1); sort(all(v2)); vector <int> :: iterator it; int MIN= sum; for (int i=0; i<sz; ++i) { int my= mid-v1[i],t1; it= lower_bound(all(v2),my); if (*(it)<=v2[sz(v2)-1]) { t1= v1[i]+ *it; MIN= min(MIN,abs(sum-2*t1)); } if (*(it)!=v2[0]) { t1= v1[i]+ *(it-1); MIN= min(MIN,abs(sum-2*t1)); } } cout<<MIN<<endl; } return 0;}
