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

#define ll long long
#define pb push_back
#define st first
#define nd second

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t;
	cin >> t;
	while(t--) {
		int n;
		string s;
		cin >> n >> s;
		int ile = 0;
		vector<pair<int, int>> v;
		for(int i=0;i<n and s[i]=='0';i++)
			ile++;
		v.pb({-2*ile, 0});
		int y = 0;
		int cos = 0;
		for(int i=ile;i<n;i++) {
			if(s[i] == '1') {
				cos++;
				v.pb({-y, 1});
				y = 0;
			} else {
				y++;
			}
		}
		v.pb({-2*y, 0});
		//for(auto x:v)
		//	cout << x.st << " ";
		//cout << "\n";
		sort(v.begin(), v.end());
		int czas = 0;
		int r = 0;
		for(int i=0;i<v.size();i++) {
			int x = -v[i].st;
			int typ = v[i].nd;
			if(typ == 0) {
				r += min(x/2, czas);
				czas++;
			} else {
				if(czas*2+1 == x) {
					r += x-1;
				} else {
					r += min(x, 2*czas+1);
				}
				czas+=2;
			}
			//cout << x << " " << typ << " " << r << "\n";
		}
		cout << r+cos << "\n";
	}
}