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

using namespace std;

int main() {
	int q;
	scanf("%d",&q);

	while (q--) {
		int n;
		scanf("%d",&n);

		int w=n;
		vector <bool> t;
		char c;
		do {c=getchar_unlocked();} while (c!='0' && c!='1');
		do {t.pb(c^'0'); c=getchar_unlocked();} while (c=='0' || c=='1');

		vector <int> s; 
		int l=t[0]?0:1;
		for (int i=1; i<n; i++) {
			if (!t[i]) {
				l++;
			} else if (!t[i-1] && l) {
				s.pb(l);
				l=0;
			}
		}
		if (l>0) s.pb(l);

		if (s.empty()) {
			printf("%d\n",n);
			continue;
		}

		if (s[0]==n) {
			puts("0");
			continue;			
		}

		int p=0;
		if (!t.front()) {
			p=s.front();
			s.erase(s.begin());
		}

		int q=0;
		if (!t.back()) {
			q=s.back();
			s.pop_back();
		}

		sort(s.begin(),s.end());

		int i=0;
		while (!s.empty() && s.back()-(i<<1)>0) {
			bool f=0;
			int h=s.back()-(i<<1);
			if (h>1) {h--; f=1;}

			if (h > p-i && h > q-i) {
				w-=h;
				s.pop_back();
				i++; if (f) i++;
			} else if (p > q) {
				w-=p-i;
				p=0;
				i++;
			} else {
				w-=q-i;
				q=0;
				i++;
			}
			
		}

		if (q > p) swap(p,q);
		if (p-i>0) {w-=p-i; i++;};
		if (q-i>0) w-=q-i;

		printf("%d\n",w);

	}

	return 0;
}