#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int g;
cin>>g;
while(g--)
{
int t;
cin>>t;
int n[t],num=0,num2;
for(int i=0;i<t;i++) cin>>n[i],num+=n[i];
num2=num;
num/=2;
//cout<<num<<endl;
int w[num+1]={0};
for(int i=0;i<t;i++)
{
for(int j=num;j>=0;j--)
{
if(n[i]>j) break;
if(w[j-n[i]]+n[i]>w[j]) w[j]=w[j-n[i]]+n[i];
}
}
cout<<(num2-w[num])-w[num]<<endl;
}
}