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 <string>
#include <math.h>
using namespace std;
int x[2][1000000];
int y[1000000];
int main()
{
int A, V=0;
cin >> A;
for(int i=0; i<A; i++)
{
int C, D=-1, E=0, F, G, H, I, J;
int B;
string s;
cin >> B;
cin >> s;
C=0;
for(int j=0; j<B+1; j++)
{
if(s[j]=='1'&&j<B)
{
x[0][C]=j-D-1;
D=j;
C=C+1;
}
if(j==B)
{
x[0][C]=j-D-1;
C=C+1;
}
}
if(C==1)
{
x[1][0]=2;
}
else
{
x[1][0]=1;
x[1][C-1]=1;
}
for(int k=0; E==0; k++)
{
	E=1;
for(int h=0; h<C-1; h++)
{
	if(x[0][h]<x[0][h+1])
	{
        F=x[0][h];
        I=x[1][h];
        x[1][h]=x[1][h+1];
        x[1][h+1]=I;
        x[0][h]=x[0][h+1];
        x[0][h+1]=F;
        E=0;
	}
}
}
G=0;
H=0;
J=0;
for(int y=0; J==0&&y<C; y++)
{
	if(x[1][y]==1&&x[0][y]-H>0)
	{
	G=G+(x[0][y]-H);
	H=H+1;
	}
	else if(x[1][y]==1&&x[0][y]-H<=0)
	{
	J=1;
	}
	if(x[1][y]==0&&x[0][y]-H-1>0)
	{
	G=G+(x[0][y]-H-1);
	H=H+2;
	}
	else if(x[1][y]==0&&x[0][y]-H-1<=0)
	{
	J=1;
	}
	if(x[1][y]==2)
	{
	G=B;
	J=1;
	}
}
y[V]=B-G;
V=V+1;
}
for(int w=0; w<V; w++)
{
cout << y[w] << "\n";
}
}