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
90
91
92
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <time.h>
#include <queue>

using namespace std;

void solve() {
	int n;
	scanf("%d\n", &n);
	vector<char> cities;
	bool one = false;
	for (int i = 0; i < n; ++i) {
		char c;
		scanf("%c", &c);
		if (c == '1') {
			one = true;
		}
		cities.push_back(c);
	}
	if (!one) {
		printf("0\n");
		return;
	}
	vector<int> lengths;
	vector<short> speeds;
	int cur = 0;
	for (int i = 0; i < n; ++i) {
		if (cities[i] == '0') {
			cur++;
		}
		else {
			if (cur > 0) {
				lengths.push_back(cur);
				speeds.push_back(2);
				cur = 0;
			}
		}
	}
	if (cur > 0) {
		lengths.push_back(cur);
		speeds.push_back(2);
	}
	if (cities[0] == '0') {
		speeds[0] = 1;
	}
	if (cities[n - 1] == '0') {
		speeds[speeds.size() - 1] = 1;
	}
	vector<pair<int, pair<int, pair<int, int> > > > q;
	for (int i = 0; i < speeds.size(); ++i) {
		q.push_back(make_pair(speeds[i] == 2 ? ((lengths[i] + 1) / 2) : lengths[i], make_pair(-speeds[i], make_pair(lengths[i], i))));
	}
	sort(q.begin(), q.end(), greater<pair<int, pair<int, pair<int, int> > > >());
	int t = 0;
	vector<int> times(q.size(), -1);
	for (int i = 0; i < q.size(); ++i) {
		int seg = q[i].second.second.second;
//		printf("POP %d %d\n", timeout, seg);
		times[seg] = t;
//		printf("t = %d\n", t);
		if ((speeds[seg] == 2) && (lengths[seg] - times[seg] * 2 <= 2)) {
			t++;
		}
		else {
			t += speeds[seg];
		}
	}
	int ret = 0;
	for (int i = 0; i < speeds.size(); ++i) {
		int saved = speeds[i] == 2 ? (((lengths[i] - 2 * times[i] + 1) / 2 == 1) ? (1) : (lengths[i] - 2 * times[i] - 1)) : (lengths[i] - times[i]);
		if (saved > 0) {
//			printf("SAVED: %d, IDX %d LEN %d TIME %d\n", saved, i, lengths[i], times[i]);
			ret += saved;
		}
	}
	printf("%d\n", n - ret);
}

int main () {
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; ++i) {
		solve();
	}
	return 0;
}