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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int  T;
char S[100000];

int result(const vector<int>& v, int minus = 0)
{
    int result = 0;
    
    for (int i = 0; i < v.size(); i++)
    {
        int value = v[i] - minus;
        
        if (value <= 0) return result;
        
        if (value == 1) result++;
        else result += value - 1;
        
        minus += 4;
    }
        
        
    return result;
}

int main(void)
{
    scanf("%d", &T);
    
    while (T--)
    {
        int len;
        int left = 0;
        vector<int> middle;
        int right = 0;
        
        scanf("%*d%s", S);
        len = strlen(S);
        
        while (S[left] == '0') left++;
        if (left < len)
        {
            while (S[len-1-right] == '0') right++;
            
            int current = 0;
            for (int i = left+1; S[i]; i++)
            {
                if (S[i] == '0') current++;
                else if (current != 0)
                {
                    middle.push_back(current);
                    current = 0;
                }
            }
            sort(middle.begin(), middle.end());
            reverse(middle.begin(), middle.end());
            
            int res1 = result(middle);
            int res2 = result(middle,2) + max(left, right);
            int res3 = result(middle,4) + left + right - 1;
            
            printf("%d\n", len-max(res1, max(res2, res3)));
        }
        else
        {
            printf("0\n");
        }
    }
    
    return 0;
}