#include<bits/stdc++.h>
using namespace std;
template<typename T>
T getNum()
{
T res=0;
char c;
while(1)
{
c=getchar_unlocked();
if(c==' '||c=='\n')
continue;
else
break;
}
res=c-'0';
while(1)
{
c=getchar_unlocked();
if(c>='0'&&c<='9')
res=10*res+c-'0';
else
break;
}
return res;
}
int main()
{
int n;
scanf("%d",&n);
for(int a=1;a<=n;a++)
{
int banyak;
banyak=getNum<int>();
int arr[banyak+3];
vector <pair<int,int> > y;
int sum=0;
for(int b=1;b<=banyak;b++)
{
arr[b]=getNum<int>();
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]));
}
}
}
printf("%d\n",sum-(jarak*2));
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdGVtcGxhdGU8dHlwZW5hbWUgVD4KVCBnZXROdW0oKQp7CglUIHJlcz0wOwoJY2hhciBjOwoJd2hpbGUoMSkKCXsKCQljPWdldGNoYXJfdW5sb2NrZWQoKTsKCQlpZihjPT0nICd8fGM9PSdcbicpCgkJCWNvbnRpbnVlOwoJCWVsc2UKCQkJYnJlYWs7Cgl9CglyZXM9Yy0nMCc7Cgl3aGlsZSgxKQoJewoJCWM9Z2V0Y2hhcl91bmxvY2tlZCgpOwoJCWlmKGM+PScwJyYmYzw9JzknKQoJCQlyZXM9MTAqcmVzK2MtJzAnOwoJCWVsc2UKCQkJYnJlYWs7Cgl9CglyZXR1cm4gcmVzOwp9CmludCBtYWluKCkKewoJaW50IG47CglzY2FuZigiJWQiLCZuKTsKCWZvcihpbnQgYT0xO2E8PW47YSsrKQoJewoJCWludCBiYW55YWs7CgkJYmFueWFrPWdldE51bTxpbnQ+KCk7CgkJaW50IGFycltiYW55YWsrM107CgkJdmVjdG9yIDxwYWlyPGludCxpbnQ+ID4geTsKCQlpbnQgc3VtPTA7CgkJZm9yKGludCBiPTE7Yjw9YmFueWFrO2IrKykKCQl7CgkJCWFycltiXT1nZXROdW08aW50PigpOwoJCQlzdW09c3VtK2FycltiXTsKCQl9CgkJc29ydChhcnIrMSxhcnIrYmFueWFrKzEpOwoJCWludCBiYXRhcz1zdW0vMjsKCQlpbnQgamFyYWs9LTE7CgkJZm9yKGludCBiPTE7Yjw9YmFueWFrO2IrKykKCQl7CgkJCWlmKGFycltiXTw9YmF0YXMpCgkJCQl5LnB1c2hfYmFjayhtYWtlX3BhaXIoYixhcnJbYl0pKTsKCQl9CQkKCQlmb3IoaW50IGI9MDtiPHkuc2l6ZSgpO2IrKykKCQl7CQkJCQoJCQlqYXJhaz1tYXgoamFyYWsseVtiXS5zZWNvbmQpOwoJCQlpZih5W2JdLnNlY29uZD09YmF0YXMpCgkJCXsKCQkJCWphcmFrPW1heChqYXJhayx5W2JdLnNlY29uZCk7CgkJCQlicmVhazsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCWZvcihpbnQgYz15W2JdLmZpcnN0JTEwKzE7Yzw9YmFueWFrO2MrKykKCQkJCXsKCQkJCQlpbnQgdGVtcD15W2JdLmZpcnN0KjEwOwoJCQkJCXRlbXA9dGVtcCtjOwkJCQkKCQkJCQlpZih5W2JdLnNlY29uZCthcnJbY108PWJhdGFzKQoJCQkJCQl5LnB1c2hfYmFjayhtYWtlX3BhaXIodGVtcCx5W2JdLnNlY29uZCthcnJbY10pKTsKCQkJCX0KCQkJfQoJCX0JCQkJCQkKCQlwcmludGYoIiVkXG4iLHN1bS0oamFyYWsqMikpOwoJfQp9