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
#include <bits/stdc++.h>
using namespace std;
constexpr int maxN = 1e5+7;

int T,n,lewo,prawo;
string s;
vector<int>grupy;

int solve(int dzien)
{
    int ans = 0;
    for(int x:grupy)
    {
        x -= 2*dzien;
        if(x <= 0)
            break;
        if(x <= 2)
        {
            ans += 1;
            dzien++;
        }
        else
        {
            ans += x-1;
            dzien+=2;
        }
    }
    return ans;
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin>>T;
while(T--)
{
    cin>>n;
    cin>>s;
    s = '!' + s;
    lewo = 0, prawo = 0;
    int j = 1;
    while(j <= n && s[j] == '0')
    {
        lewo++;
        j++;
    }
    j = n;
    while(j >= 1 && s[j] == '0')
    {
        prawo++;
        j--;
    }

    if(lewo == n)
    {
        cout<<0<<"\n";
        continue;
    }
    grupy.clear();
    //grupy.shrink_to_fit();
    int c = 0; /// ile ma grupa
    for(int i=lewo+1;i<=n-prawo;i++)
    {
        if(s[i] == '1')
        {
            if(c)
                grupy.push_back(c);
            c = 0;
        }
        else
            c++;
    }
    if(c)
        grupy.push_back(c);
    sort(grupy.begin(), grupy.end(), greater<int>());
    int ans = max({solve(1)+lewo, solve(1)+prawo, solve(2)+max(lewo,prawo)+min(lewo,prawo)-1 , solve(0)});
    cout<<n-ans<<"\n";
}
}
/*

3
8
00110100
10
1001000010
4
0000

*/