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
#include <cstdio>
#include <set>
using namespace std;

#define MAX_N	100010

typedef pair<int, int> PII;

int T, N;
char M[MAX_N];

struct cmp {
	bool operator() (const PII& lhs, const PII& rhs) const {
		return lhs.first != rhs.first ? rhs.first < lhs.first : lhs.second < rhs.second;
	}
};

multiset<PII, cmp> s;

int c0, c1;

void slv() {
	scanf("%d", &N);
	scanf("%s", M);

	s.clear();
	c0 = c1 = 0;

	for (int i = 0; i < N; ++i) {
		if (M[i] == '1') {
			if (c0) {
				if (!c1) {
					s.insert(make_pair(2 * c0, 1));
				} else {
					s.insert(make_pair(c0, 2));
				}
				c0 = 0;
			}
			c1++;
		} else {
			c0++;
		}
	}
	if (c0) {
		s.insert(make_pair(2 * c0, 1));
	}

	if (!c1) {
		printf("0\n");
		return;
	}

	c0 = c1 = 0;
	for (auto it = s.begin(); it != s.end() && it->first > 2 * c0; it++) {
		switch (it->second) {
			case 1:
				c1 += it->first / 2 - c0;
				c0++;
				break;
			case 2:
				if (it->first > 2 * c0 + 1) {
					c1 += it->first - 2 * c0 - 1;
					c0 += 2;
				} else {
					c1 += it->first - 2 * c0;
					c0++;
				}
				break;
		}
	}

	printf("%d\n", N - c1);
}

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