#include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int maxm = 1e5+;

 int a[maxn];

 int dp[maxm];

 int T, n, m;

 int main()

 {

     cin >> T;

     while(T--)

     {

         cin >> n;

         int sum = ;

         memset(dp, , sizeof(dp));

         for(int i = ; i < n; i++)cin >> a[i], sum += a[i];

         for(int i = ; i < n; i++)

         {

             for(int j = sum / ; j >= a[i]; j--)

                 dp[j] = max(dp[j], dp[j - a[i]] + a[i]);

         }

         cout<<(sum -  * dp[sum / ])<<endl;

     }

     return ;

 }