//Ishan Bansal
//handle:ishan.nitj at codeforces ,ishan_nitj at codechef
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000000000000
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define print_array(a,n) for(i=0;i<n;i++) printf("%lld ",a[i]);
#define mset(x,v) memset(x, v, sizeof(x))
#define dbg1(x) cout<<#x<<" "<<x<<endl;
#define dbg2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define dbg4(x,y,z,k) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<" "<<#k<<" "<<k<<endl;
#define pb push_back
#define fe first
#define se second
#define mag 12
   ll subset[250000+1][500+1];
 ll balancePartition(ll set[], ll n)
{
 /*The value of subset[i][j] will be true if there is a subset 
     of set[0..j-1] with sum equal to i */
        ll i,j;
        ll sum =0;
 
        for(i =0; i<=n; i++){
                sum += set[i];
        }
 

        // If sum is 0, then answer is true
        for (i = 0; i <= n; i++)
                subset[0][i] = true;
 
        // If sum is not 0 and set is empty, then answer is false
        for (i = 1; i <= sum; i++)
                subset[i][0] = false;
 
 
        // Fill the subset table in botton up manner
        for (i = 1; i <= sum; i++)
        {
         for ( j = 1; j <= n ; j++)
         {
           subset[i][j] = subset[i][j-1];
           if (i >= set[j-1]){
              subset[i][j] = subset[i][j] ||subset[i-set[j-1]][j-1];
           }
         }
        }
 
        ll min =inf;
    
        for(i=1; i<=sum; i++){
           for(j=1; j<=n; j++){
           /* If there is s subset with sum i, then check if the 
              difference between overall sum and twice this sum is least or not.
              If yes update the min */
              
              if(subset[i][j] == true){
                   if(abs(sum - 2*i) < min){
                       min  = abs(sum - 2 *i);
                   }
              }
           }
        }
 
return min;
}
 
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
//freopen("OP.txt","r",stdin);
//freopen("IP.txt","w",stdout);
ll t;cin>>t;
while(t--){
mset(subset,0);
ll n;cin>>n;
ll i;
vector<ll>v;
rep(i,n){
ll x;string s;
cin>>x>>s;
v.pb(x);
}
ll x;cin>>x;v.pb(x);
vector<ll>v1,v2;
for(i=0;i<v.size();i++){
if(i%2==0)
v1.pb(v[i]);
else
v2.pb(v[i]);
}
ll arr1[v1.size()],arr2[v2.size()];
for(i=0;i<v1.size();i++)
arr1[i]=v1[i];
for(i=0;i<v2.size();i++)
arr2[i]=v2[i];
ll ans=balancePartition(arr1,v1.size()-1)+balancePartition(arr2,v2.size()-1);
cout<<ans<<endl;
}
 
}