#include "bits/stdc++.h"
using namespace std;
const int N = 505;
int t;
int n;
int arr[N];
bitset < N * N > bit;
int solve(vector < int > &v){
	int sum = 0;
	for(int x : v){
		sum += x;
	}
	bit.reset();
	bit.set(0);
	for(int x : v){
		bit |= (bit << x);
	}
	int ans = sum;
	for(int i = 0 ; i < sum ; ++i){
		if(bit.test(i)){
			ans = min(ans , abs(i - (sum - i)));
		}
	}
	return ans;
}
int main(){
	scanf("%d" , &t);
	while(t--){
		scanf("%d" , &n);
		char ty[3];
		for(int i = 0 ; i < n ; ++i){
			scanf("%d %s" , arr + i , ty);
		}
		scanf("%d" , &arr[n]);
		if(n <= 2){
			printf("NO\n");
			continue;
		}
		vector < int > v1;
		vector < int > v2;
		v1.clear();
		v2.clear();
		for(int i = 0 ; i <= n ; i += 2){
			v1.emplace_back(arr[i]);
		}
		for(int i = 1 ; i <= n ; i += 2){
			v2.emplace_back(arr[i]);
		}
		printf("%d\n" , solve(v1) + solve(v2));
	}
}