#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

typedef short sh;
sh n;
short a[107];
map<pair<int,pair<int,int> >,bool > mp;
priority_queue<pair<sh,pair<sh,sh> > > pq;
int main(){

    int t;
    cin>>t;
    while(t--){

    memset(a,0,sizeof a);
cin>>n;
for(int i=1;i<1+n;i++)
    cin>>a[i];
    pq.push({0,{0,0}});
    sh fact=0;
    sh ans=300;
    mp.clear();
     while(!pq.empty())
    {

        pair<sh,pair<sh,sh > >moth=pq.top();
        fact=-1*moth.first;
         pq.pop();
                 if(mp[moth])continue;
                 mp[moth]=1;

         sh z=moth.second.second;
        sh y=moth.second.first+1;
        if(y==n+1){

                ans=min(ans,fact);

        continue;
        }
        if(fact>=ans)continue;
           // cout<<fact<<' '<<y<<endl;
              pq.push({-1*max(fact,(sh)abs(z+a[y])),{(sh)y,(sh)a[y]+z}});
             pq.push({-1*max(fact,(sh)abs(z-a[y])),{y,z-a[y]}});

     }
     cout<<ans<<endl;;
    }

         return 0;
}