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

int z,n,dp[100005];

string s;

priority_queue < pair<int,int> > Q;

stack < pair< pair<int,int> ,int> > S;


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

    cin>>z;
    while(z)
    {
        z--;
        cin>>n>>s;
        int dl = 0;
        for(int i = n - 1;i >= 0; i--)
            if(s[i] == '0')
                dl++;
            else
                break;
        if(dl == n)
        {
            cout<<"0\n";
            continue;
        }
        if(dl > 0)
            Q.push({dl + 100000,1});
        dl = 0;
        for(int i = 0;i < n; i++)
            if(s[i] == '0')
                dl++;
            else
                break;
        if(dl > 0)
            Q.push({dl + 100000,1});
        int dl2 = 0;
        for(int i = dl;i < n; i++)
            if(s[i] == '0')
                dl2++;
            else if(dl2 > 0)
            {
                Q.push({dl2,min(dl2,2)});
                dl2 = 0;
            }
        int maxDzien = 0,dzien;
        while(!Q.empty())
        {
            dzien = 0;
            int x = Q.top().first,dx = Q.top().second;
            if(x > 100000)
                x -= 100000;
            Q.pop();
            maxDzien = max(maxDzien,x / dx + x % dx);
            for(int i = 1;i <= maxDzien; i++)
            	dp[i] = max(dp[i],dp[i - 1]);
            while(x > 0)
            {
                dx = min(dx,x);
                S.push({{x - (dx - 1),dzien},dx});
                dzien++;
                x -= dx;
            }
            while(!S.empty())
            {
                int a = S.top().first.first;
                int b = S.top().first.second;
                int c = S.top().second;
                S.pop();
                dp[b + c] = max(dp[b + c],dp[b] + a);
            }
        }
        int wyn = 0;
        for(int i = 0;i <= maxDzien + 2; i++)
        {
            wyn = max(wyn,dp[i]);
            dp[i] = 0;
        }
        cout<<n - wyn<<'\n';
    }
    return 0;
}