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

void solve(){

	ll n, f = -5, l = -5, strike = 0, one= 0;
	ll a, b;
	char tmp;
	priority_queue<ll>Q, E;

	cin >> n;
	bool tab[n+7];

	for(int i = 1; i <= n; i++){
		cin >> tmp;

		if(tmp == '1'){
			tab[i] = 1;
			l = n - i;

			if(strike!=0 and f!=-5){
				Q.push(strike);
			}
			strike = 0;

			if(f == -5) f = i -1;
			one++;
		}
		else{
			tab[i] = 0;
			strike++;
		}
	}

	if(!one){cout << 0 << "\n"; return;}

	//cout << f << " " << l << "\n";
	if(f!=-5 and f!=0) E.push(f); 
	if(l!=0) E.push(l);

	int t = 0;
	int vacc = 0;
	while(!Q.empty() or !E.empty()){

		if(!Q.empty()) a = Q.top() - 2*t;
		else a = -1e10;

		if(!E.empty()) b = E.top() - t;
		else b = -1e10;


		if(max(a,b) <= 0) break;
		if(a-2 > b or b <= 0){
			Q.pop();
            if(a > 2){ vacc += a-1; t+=2;}
            else{ vacc += a; t++;}
		}
		else{
			E.pop();
			vacc += b;
			t++;
		}
		//cout << a << " " << b << "   " << vacc << "\n";
	}
	cout << n - vacc << "\n";
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
		solve();
	}
}

/*
561 test

20
00010000010100101000

prawidlowa: 14
moja: 15
*/