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
93
94
95
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		int n;
		string s;
		cin >> n;
		cin >> s;
		vector<int> t1, t2;
		int i1 = s.find_first_of("1");
		if (i1 == string::npos){
			cout << "0" << "\n";
			continue;
		}
		t2.push_back(i1);
		int i2 = s.find_last_of("1");
		t2.push_back(n - 1 - i2);
		int last = i1;
		for (int i = i1 + 1; i <= i2; i++){
			if (s[i] == '1'){
				//if (i - last - 1 == 9)
				//cout << "ww " << i << "\n"; 
				t1.push_back(i - last - 1);
				last = i;
			}
		}
		sort(t1.begin(), t1.end(), greater<int>());
		sort(t2.begin(), t2.end(), greater<int>());
		int day = 0;
		int res = 0;
		int superday = 0;
		int res2 = 0, res3 = 0, res4 = 0;
		while (t1.size() > day / 2){
			int l = t1[day / 2];
			//cout << "ss " << l << " " << res << "\n";
			if (l - 2 * day == 5){
				res2 = res + 1;
				int day2 = day;
				res2 += max(0, t2[0] - day2);
				day2++;
				res2 += max(0, t2[1] - day2);
				day2++; 
			}
			if (l - 2 * day <= 4){
				if (l - 2 * day <= 0){
					break;
				}
				res4 = res;
				int day4 = day;
				res4 += max(0, t2[0] - day4);
				day4++;
				res4 += max(0, t2[1] - day4);
				if ((l - 2 * day >= 3) && (l - 2 * day <= 4)){
					int day3 = day;
					res3 = res + 1;
					res3 += t2[0] - day3;
					day3 += 2;
					res3 += max(0, t2[1] - day3);
					day3++;
				}
				if (l - 2 * day == 4){
					res += 3;
					day += 2;
				}
				else if (l - 2 * day == 3){
					res += 2;
					day += 2;
				}
				else if (l - 2 * day == 2){
					res += 1;
					day++;
				}
				else {
					res += 1;
					day++;
				}
				break;
			}
			res += l - 2 * day - 1;
			day += 2;
		}
		for (int i = 0; i < t2.size(); i++){
			res += max(0, t2[i] - day);
			day++;
		}
		//cout << n - res << " " << n - res2 << " " << n - res3 << "\n";
		cout << min(min(n - res, n - res2), min(n - res3, n - res4)) << "\n";
	}
}