//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;
}
}
Ly9Jc2hhbiBCYW5zYWwKLy9oYW5kbGU6aXNoYW4ubml0aiBhdCBjb2RlZm9yY2VzICxpc2hhbl9uaXRqIGF0IGNvZGVjaGVmCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGluZiAxMDAwMDAwMDAwMDAwMDAwMDAwCiNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKI2RlZmluZSByZXAoaSxuKSBmb3IoaT0wO2k8bjtpKyspCiNkZWZpbmUgcHJpbnRfYXJyYXkoYSxuKSBmb3IoaT0wO2k8bjtpKyspIHByaW50ZigiJWxsZCAiLGFbaV0pOwojZGVmaW5lIG1zZXQoeCx2KSBtZW1zZXQoeCwgdiwgc2l6ZW9mKHgpKQojZGVmaW5lIGRiZzEoeCkgY291dDw8I3g8PCIgIjw8eDw8ZW5kbDsKI2RlZmluZSBkYmcyKHgseSkgY291dDw8I3g8PCIgIjw8eDw8IiAiPDwjeTw8IiAiPDx5PDxlbmRsOwojZGVmaW5lIGRiZzMoeCx5LHopIGNvdXQ8PCN4PDwiICI8PHg8PCIgIjw8I3k8PCIgIjw8eTw8IiAiPDwjejw8IiAiPDx6PDxlbmRsOwojZGVmaW5lIGRiZzQoeCx5LHosaykgY291dDw8I3g8PCIgIjw8eDw8IiAiPDwjeTw8IiAiPDx5PDwiICI8PCN6PDwiICI8PHo8PCIgIjw8I2s8PCIgIjw8azw8ZW5kbDsKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBmZSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIG1hZyAxMgogICBsbCBzdWJzZXRbMjUwMDAwKzFdWzUwMCsxXTsKIGxsIGJhbGFuY2VQYXJ0aXRpb24obGwgc2V0W10sIGxsIG4pCnsKIC8qVGhlIHZhbHVlIG9mIHN1YnNldFtpXVtqXSB3aWxsIGJlIHRydWUgaWYgdGhlcmUgaXMgYSBzdWJzZXQgCiAgICAgb2Ygc2V0WzAuLmotMV0gd2l0aCBzdW0gZXF1YWwgdG8gaSAqLwogICAgICAgIGxsIGksajsKICAgICAgICBsbCBzdW0gPTA7CiAKICAgICAgICBmb3IoaSA9MDsgaTw9bjsgaSsrKXsKICAgICAgICAgICAgICAgIHN1bSArPSBzZXRbaV07CiAgICAgICAgfQogCgogICAgICAgIC8vIElmIHN1bSBpcyAwLCB0aGVuIGFuc3dlciBpcyB0cnVlCiAgICAgICAgZm9yIChpID0gMDsgaSA8PSBuOyBpKyspCiAgICAgICAgICAgICAgICBzdWJzZXRbMF1baV0gPSB0cnVlOwogCiAgICAgICAgLy8gSWYgc3VtIGlzIG5vdCAwIGFuZCBzZXQgaXMgZW1wdHksIHRoZW4gYW5zd2VyIGlzIGZhbHNlCiAgICAgICAgZm9yIChpID0gMTsgaSA8PSBzdW07IGkrKykKICAgICAgICAgICAgICAgIHN1YnNldFtpXVswXSA9IGZhbHNlOwogCiAKICAgICAgICAvLyBGaWxsIHRoZSBzdWJzZXQgdGFibGUgaW4gYm90dG9uIHVwIG1hbm5lcgogICAgICAgIGZvciAoaSA9IDE7IGkgPD0gc3VtOyBpKyspCiAgICAgICAgewogICAgICAgICBmb3IgKCBqID0gMTsgaiA8PSBuIDsgaisrKQogICAgICAgICB7CiAgICAgICAgICAgc3Vic2V0W2ldW2pdID0gc3Vic2V0W2ldW2otMV07CiAgICAgICAgICAgaWYgKGkgPj0gc2V0W2otMV0pewogICAgICAgICAgICAgIHN1YnNldFtpXVtqXSA9IHN1YnNldFtpXVtqXSB8fHN1YnNldFtpLXNldFtqLTFdXVtqLTFdOwogICAgICAgICAgIH0KICAgICAgICAgfQogICAgICAgIH0KIAogICAgICAgIGxsIG1pbiA9aW5mOwogICAgCiAgICAgICAgZm9yKGk9MTsgaTw9c3VtOyBpKyspewogICAgICAgICAgIGZvcihqPTE7IGo8PW47IGorKyl7CiAgICAgICAgICAgLyogSWYgdGhlcmUgaXMgcyBzdWJzZXQgd2l0aCBzdW0gaSwgdGhlbiBjaGVjayBpZiB0aGUgCiAgICAgICAgICAgICAgZGlmZmVyZW5jZSBiZXR3ZWVuIG92ZXJhbGwgc3VtIGFuZCB0d2ljZSB0aGlzIHN1bSBpcyBsZWFzdCBvciBub3QuCiAgICAgICAgICAgICAgSWYgeWVzIHVwZGF0ZSB0aGUgbWluICovCiAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgaWYoc3Vic2V0W2ldW2pdID09IHRydWUpewogICAgICAgICAgICAgICAgICAgaWYoYWJzKHN1bSAtIDIqaSkgPCBtaW4pewogICAgICAgICAgICAgICAgICAgICAgIG1pbiAgPSBhYnMoc3VtIC0gMiAqaSk7CiAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgfQogICAgICAgICAgIH0KICAgICAgICB9CiAKcmV0dXJuIG1pbjsKfQogCmludCBtYWluKCl7CnN0ZDo6aW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwpjaW4udGllKDApOwovL2ZyZW9wZW4oIk9QLnR4dCIsInIiLHN0ZGluKTsKLy9mcmVvcGVuKCJJUC50eHQiLCJ3IixzdGRvdXQpOwpsbCB0O2Npbj4+dDsKd2hpbGUodC0tKXsKbXNldChzdWJzZXQsMCk7CmxsIG47Y2luPj5uOwpsbCBpOwp2ZWN0b3I8bGw+djsKcmVwKGksbil7CmxsIHg7c3RyaW5nIHM7CmNpbj4+eD4+czsKdi5wYih4KTsKfQpsbCB4O2Npbj4+eDt2LnBiKHgpOwp2ZWN0b3I8bGw+djEsdjI7CmZvcihpPTA7aTx2LnNpemUoKTtpKyspewppZihpJTI9PTApCnYxLnBiKHZbaV0pOwplbHNlCnYyLnBiKHZbaV0pOwp9CmxsIGFycjFbdjEuc2l6ZSgpXSxhcnIyW3YyLnNpemUoKV07CmZvcihpPTA7aTx2MS5zaXplKCk7aSsrKQphcnIxW2ldPXYxW2ldOwpmb3IoaT0wO2k8djIuc2l6ZSgpO2krKykKYXJyMltpXT12MltpXTsKbGwgYW5zPWJhbGFuY2VQYXJ0aXRpb24oYXJyMSx2MS5zaXplKCktMSkrYmFsYW5jZVBhcnRpdGlvbihhcnIyLHYyLnNpemUoKS0xKTsKY291dDw8YW5zPDxlbmRsOwp9CiAKfSAKCg==