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
#include<bits/stdc++.h>

using namespace std;

template<class T> ostream& operator<<(ostream& os, vector<T> &vec) {
	os << "{ ";
	for (auto x : vec)
		os << x << " ";
	return os << "}";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int tests; cin >> tests;
	for (int task = 0; task < tests; task++) {
		int n; cin >> n;
		string s; cin >> s;
		vector<int> ones = {0, 0};
		vector<int> twos;
		while (ones[0] < n and s[ones[0]] == '0')
			ones[0]++;
		if (ones[0] == n) {
			cout << 0 << "\n";
			continue;
		}
		while (ones[1] < n and s[n - 1 - ones[1]] == '0')
			ones[1]++;
		for (int i = ones[0]; i < n - ones[1]; i++) {
			if (s[i] == '0') {
				twos.emplace_back(1);
				while (i < n - 1 and s[i + 1] == '0') {
					i++;
					(twos.back())++;
				}
			}
		}
		sort(ones.begin(), ones.end());
		sort(twos.begin(), twos.end());
		/* cerr << "ones = " << ones << "\n";	
		cerr << "twos = " << twos << "\n"; */
		int t = 0;
		int ans = 0;
		while (not ones.empty() or not twos.empty()) {
			int x = 0;
			if (not ones.empty()) 
				x = ones.back();
			int y = 0;
			if (not twos.empty()) 
				y = twos.back();
			int x_profit = max(x - t, 0);
			int y_profit = y - 2 * t == 1 ? 1 : max(y - 2 * t - 1, 0);
			if (y_profit > x_profit or ones.empty()) {
				ans += y_profit;
				if (y_profit == 1) t += 1;
				if (y_profit > 1) t += 2;
				twos.pop_back();
			} else {
				ans += x_profit;
				if (x - t > 0)
					t += 1;
				ones.pop_back();
			}
		}
		cout << n - ans << "\n";
	}
}