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

//#define int long long
#define st first
#define nd second
#define bg begin
#define ed end
#define pb push_back
#define all(r) bg(r),ed(r)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) 

int32_t main(){
	fast;
	int z;
	cin>>z;
	while(z--){
		int n;
		cin>>n;
		vector<char>in(n);
		for(auto& x:in){
			cin>>x;
		}
		vector<int>v;
		int p=0;
		int q=0;
		int i=0;
		while(i<n&&in[i]=='0'){
			p++;
			i++;
		}
		int j=n-1;
		while(j>=0&&in[j]=='0'){
			q++;
			j--;
		}
		if(p>q){
			swap(p,q);
		}
		int c=0;
		for(i;i<=j;i++){
			char x;
			x=in[i];
			if(x=='0'){
				c++;
			}else{
				v.pb(c);
				c=0;
			}
		}
		if(v.size()==0){
			cout<<0<<'\n';
			continue;
		}
		sort(all(v),greater<int>());
		int ind=0;
		int day=0;
		int res=0;
		while(ind<(int)v.size()&&(v[ind]-2*day>0||p-day>0||q-day>0)){
			if(2*(p-day)>v[ind]-2*day-1&&p-day>0){
				res+=p-day;
				p=0;
				day++;
			}else if(2*(q-day)>v[ind]-2*day-1&&q-day>0){
				res+=q-day;
				q=0;
				day++;
			}else{
				if(v[ind]-2*day>2){
					res+=v[ind]-1-2*day;
					ind++;
					day+=2;
				}else{
					res++;
					ind++;
					day++;
				}
			}
			//cout<<res<<'\n';
		}
		cout<<n-res<<'\n';
	}
}