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
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
 
int main()
{
    int k, n;
    scanf("%d",&k);
    for (int o=0; o<k; o++)
    {
        scanf("%d",&n);
        char c[n];
        scanf("%s",c);

        vector<int> v;
        int begin = 0, end = 0;
        int len = 0;
        bool beginAdded = c[0] == '1';
        for (int i=0; i<n; i++)
        {
            if (c[i] == '0')
                len++;
            else
            {
                if (len > 0)
                {
                    if (beginAdded)
                        v.push_back(len);
                    else
                        begin = len;
                    beginAdded = true;
                }
                len=0;
            }
        }
        end = len;

        sort(v.begin(), v.end(), greater<int>());

        int x1=0,x2=0,x3=0;
        if (begin > end)
            x2 = begin;
        else
            x2 = end;
        x3 = begin+end-1;

        for (int i=0;i<v.size(); i++)
        {
            if (v[i] - 4*i - 1 > 0)
                x1 += v[i] - 4*i - 1;
            else if (v[i] - 4*i == 1)
                x1++;
            if (v[i] - 4*i - 3 > 0)
                x2 += v[i] - 4*i - 3;
            else if (v[i] - 4*i - 2 == 1)
                x2++;
            if (v[i] - 4*i - 5 > 0)
                x3 += v[i] - 4*i - 5;
            else if (v[i] - 4*i - 4 == 1)
                x3++;
        }

        printf("%d\n",n-max(x1,max(x2,x3)));
    }

}