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
#include <bits/stdc++.h>
using namespace std;
int n,w,pom,pom1,ggg,poc,kon,fg;
char z;
vector<int>t;
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	cin>>ggg;
	for(int jk=0; jk<ggg; jk++)
	{
		cin>>n;
		t.clear();
		w=0;
		fg=0;
		t.push_back(0);
		for(int j=0; j<n; j++)
		{
			cin>>z;
			if(z=='0')
			{
				pom++;
				fg++;
			}
			else
			{
				if(pom==j)
				{
					poc=pom;
					
				}
				else
				{
					t.push_back(pom);
				}
				pom=0;
			}
		}
		kon=pom;
		sort(t.begin(), t.end());
		pom=0;
		pom1=t.size()-1;
		while(pom1>0&&(t[pom1]-2*pom-1>=0||poc-pom>0||kon-pom>0))
		{
			//cout<<t[pom1]<<" "<<poc<<" "<<kon<<"\n";
			if(poc-pom>t[pom1]-2*pom-1&&poc-pom>kon-pom)
			{
				w+=poc-pom;
				pom++;
				poc=0;
			//	cout<<"poc";
			}
			else
			{
				if(kon-pom>t[pom1]-2*pom-1)
				{
					w+=kon-pom;
					kon=0;
					pom++;
					//cout<<"kon";
				}
				else
				{
					if(t[pom1]-2*pom-1==0)
					{
						w+=t[pom1]-2*pom;
						pom++;
						pom1--;
					//	cout<<"sus";
					}
					else
					{
						w+=t[pom1]-2*pom-1;
						pom+=2;
						pom1--;
						//cout<<"sus";
					}
				}
			}
		//	cout<<w;
		}
		if(fg==n)
		cout<<"0\n";
		else
		cout<<n-w<<"\n";
	}
}