dp

using namespace std;

#include<iostream>
#include<cstring>
#include<cmath>

#define max(a,b) (((a)>(b))?(a):(b))
#define N 50000

//int max(int a, int b) { return (a > b)? a : b; }

/*int iabs(int n)
{
    return (n > 0)? n : -n;
}*/

int dp[105][N],val[N],n,maxV;

int solve(int item,int W)
{
    if(item>n)
        return 0;
    if(dp[item][W]!=-1)
        return dp[item][W];

    if(maxV>=(W+val[item]))
        return dp[item][W] = max(val[item]+solve(item+1,W+val[item]),solve(item+1,W));
    else
        return dp[item][W] = solve(item+1,W);
}

int main()
{
    int T;
    cin>>T;

    while(T--)
    {
        int sum=0;
        memset(dp,-1,sizeof(dp));
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>val[i];
            sum+=val[i];
        }
       /* if(sum%2)
            maxV = (sum/2)+1;
        else*/
            maxV = sum/2;
        int ans = solve(1,0);
        cout<<(sum-ans)-ans<<endl;
    }
    return 0;
}