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

struct ciag {
	double poilu;
	int dlug, str;
};

void DO() {
	int n;
	cin >> n;
	int ile = 0;
	vector <ciag> v;
	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		if (c == '0')
			ile++;
		else if (ile) {
			ciag temp = {(double)ile / 2, ile, 2};
			if (i == ile) {
				temp.str = 1;
				temp.poilu = ile;
			}
			v.emplace_back(temp);
			ile = 0;
		}
	}
	if (ile) {
		if (ile == n) {
			cout << "0\n";
			return;
		}
		ciag temp = {(double)ile, ile, 1};
		v.emplace_back(temp);
	}
	sort(v.rbegin(), v.rend(), [&](auto a, auto b) {return a.poilu < b.poilu;});
	int dni = 0, res = 0;
	for (int i = 0; i < (int)v.size(); i++) {
		v[i].dlug -= v[i].str * dni;
		if (v[i].dlug > 0) { 
			dni++;
			if (v[i].dlug > 1 && v[i].str == 2) {
				v[i].dlug--;
				dni++;
			}
			res += v[i].dlug;
		}
		else
			break;
	}
	cout << n - res << "\n";
	return;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while (t--)
		DO();
	return 0;
}