1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int tt;
	cin >> tt;
	while (tt --> 0) {
		int n;
		cin >> n;
		string s;
		cin >> s;
		bool all_zero = true;
		REP(i,n) {
			if (s.at(i) != '0') {
				all_zero = false;
			}
		}
		if (all_zero) {
			cout << 0 << '\n';
			continue;
		}
		vector<int> v1 = {n + 10}, v2 = {n + 10};
		int left = 0;
		int right = n - 1;
		if (s.at(0) == '0') {
			while (s.at(left) == '0') {
				++left;
			}
			v1.emplace_back(left);
		}
		if (s.at(right) == '0') {
			while (s.at(right) == '0') {
				--right;
			}
			v1.emplace_back(n - 1 - right);
		}
		sort(v1.begin(), v1.end());
		reverse(v1.begin(), v1.end());
		while (left < right) {
			while (left < n && s.at(left) == '1') {
				++left;
			}
			if (left >= right) {
				break;
			}
			int start = left;
			while (s.at(left) == '0') {
				++left;
			}
			v2.push_back(left - start);
		}
		sort(v2.begin(), v2.end());
		reverse(v2.begin(), v2.end());
		debug(v1, v2);
		vector<vector<int>> dp(ssize(v1), vector<int>(ssize(v2)));
		REP(i,ssize(v1)) {
			REP(j,ssize(v2)) {
				debug(i,j);
				if (i > 0) {
					int cur = max(0, v1[i] - (i - 1) - 2 * j);
					dp[i][j] = max(dp[i][j], dp[i - 1][j] + cur);
				}
				if (j > 0) {
					int cur = max(0, v2[j] - 2 * i - 4 * (j - 1));
					if (cur > 0) {
						cur = max(1, cur - 1);
					}
					dp[i][j] = max(dp[i][j], dp[i][j - 1] + cur);
				}
			}
		}
		debug(dp);
		int ans = n - dp[ssize(v1) - 1][ssize(v2) - 1];
		cout << ans << '\n';
	}
}