#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
for(int a=1;a<=n;a++)
{
int banyak;
scanf("%d",&banyak);
int arr[banyak+3];
vector <pair<int,int> > y;
int sum=0;
for(int b=1;b<=banyak;b++)
{
scanf("%d",&arr[b]);
sum=sum+arr[b];
}
sort(arr+1,arr+banyak+1);
int batas=sum/2;
int jarak=-1;
for(int b=1;b<=banyak;b++)
{
if(arr[b]<=batas)
y.push_back(make_pair(b,arr[b]));
}
for(int b=0;b<y.size();b++)
{
jarak=max(jarak,y[b].second);
if(y[b].second==batas)
{
jarak=max(jarak,y[b].second);
break;
}
else
{
for(int c=y[b].first%10+1;c<=banyak;c++)
{
int temp=y[b].first*10;
temp=temp+c;
if(y[b].second+arr[c]<=batas)
y.push_back(make_pair(temp,y[b].second+arr[c]));
}
}
}
/*for(int b=0;b<y.size();b++)
{
printf("%d ",y[b].first);
}
printf("\n");
printf("jarak=%d\n",jarak);*/
printf("%d\n",sum-(jarak*2));
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG1haW4oKQp7CglpbnQgbjsKCXNjYW5mKCIlZCIsJm4pOwoJZm9yKGludCBhPTE7YTw9bjthKyspCgl7CgkJaW50IGJhbnlhazsKCQlzY2FuZigiJWQiLCZiYW55YWspOwoJCWludCBhcnJbYmFueWFrKzNdOwoJCXZlY3RvciA8cGFpcjxpbnQsaW50PiA+IHk7CgkJaW50IHN1bT0wOwoJCWZvcihpbnQgYj0xO2I8PWJhbnlhaztiKyspCgkJewoJCQlzY2FuZigiJWQiLCZhcnJbYl0pOwoJCQlzdW09c3VtK2FycltiXTsKCQl9CgkJc29ydChhcnIrMSxhcnIrYmFueWFrKzEpOwoJCWludCBiYXRhcz1zdW0vMjsKCQlpbnQgamFyYWs9LTE7CgkJZm9yKGludCBiPTE7Yjw9YmFueWFrO2IrKykKCQl7CgkJCWlmKGFycltiXTw9YmF0YXMpCgkJCQl5LnB1c2hfYmFjayhtYWtlX3BhaXIoYixhcnJbYl0pKTsKCQl9CQkKCQlmb3IoaW50IGI9MDtiPHkuc2l6ZSgpO2IrKykKCQl7CQkJCQoJCQlqYXJhaz1tYXgoamFyYWsseVtiXS5zZWNvbmQpOwoJCQlpZih5W2JdLnNlY29uZD09YmF0YXMpCgkJCXsKCQkJCWphcmFrPW1heChqYXJhayx5W2JdLnNlY29uZCk7CgkJCQlicmVhazsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCWZvcihpbnQgYz15W2JdLmZpcnN0JTEwKzE7Yzw9YmFueWFrO2MrKykKCQkJCXsKCQkJCQlpbnQgdGVtcD15W2JdLmZpcnN0KjEwOwoJCQkJCXRlbXA9dGVtcCtjOwkJCQkKCQkJCQlpZih5W2JdLnNlY29uZCthcnJbY108PWJhdGFzKQoJCQkJCQl5LnB1c2hfYmFjayhtYWtlX3BhaXIodGVtcCx5W2JdLnNlY29uZCthcnJbY10pKTsKCQkJCX0KCQkJfQoJCX0JCQoJCS8qZm9yKGludCBiPTA7Yjx5LnNpemUoKTtiKyspCgkJewoJCQlwcmludGYoIiVkICIseVtiXS5maXJzdCk7CgkJfQoJCXByaW50ZigiXG4iKTsKCQlwcmludGYoImphcmFrPSVkXG4iLGphcmFrKTsqLwoJCQoJCXByaW50ZigiJWRcbiIsc3VtLShqYXJhayoyKSk7Cgl9Cn0=