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

int a[1000007];
int c[1000007];



int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t, n, licznik=0, h=0, pierwszy=0, ostatni=0, czy1=0, ile=0, wynik=0, xd=0;
string s;
cin >> t;
for (int j=1; j<=t; j++) {
    cin >> n;
    cin >> s;
    if (s=="101") {
        cout << 2 << "\n";
        continue;
    }
   if (s[0]=='1') {
        czy1=1;
    }
    for (int i=0; i<s.size(); i++) {
        if (s[i]=='0') {
            licznik++;
        }

         if (s[i]=='1' and czy1==1) {
                if (licznik>0)
            a[++h]=licznik;
            c[h]=0;
            licznik=0;
        }
        if (s[i]=='1' and czy1==0) {
            pierwszy=licznik;
            licznik=0;
            czy1=1;
        }
    }
    if (s[s.size()-1]=='0') {
        ostatni=licznik;
    }

sort(a+1,a+1+h);
reverse(a+1,a+1+h);
ile=0;
pierwszy+=2;
ostatni+=2;
if (h==0) {
    h++;
}
    for (int i=1; i<=h; i++) {
            pierwszy=max(0,pierwszy-2+xd);
            ostatni=max(0,ostatni-2+xd);
            a[i]=max(0,a[i]-ile+max(0,((c[i]-1)*2)));
            if (a[i]<=0 and pierwszy<=0 and ostatni<=0) {
                break;
            }
            if(a[i]>max(pierwszy,ostatni) and (a[i]!=3 and max(pierwszy,ostatni)!=2)) {
                    if (a[i]>1)
                wynik+=a[i]-1;
            else wynik+=1;
                ile+=4;
                xd=0;
            }
            else {
                wynik+=max(pierwszy,ostatni);
                if (pierwszy>ostatni)
                    pierwszy=0;
                else ostatni=0;
                ile+=2;
                xd=1;
                   c[i]++;
                i--;
            }
    }

           h=0;
           pierwszy=0;
           ostatni=0;
           czy1=0;
           licznik=0;
           cout << max(0,n-wynik) << "\n";
           wynik=0;
           xd=0;
           ile=0;
}







return 0;
}