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

using namespace std;

int Count(int t, vector<int> a, vector<int> x)
{
    int res = 0;
    while (!a.empty() || !x.empty()) {
        if (a.empty()) {
            if (x.back() < 2 * t + 1)
                break;
            if (x.back() == 2 * t + 1) {
                res++;
                break;
            }
            res += x.back() - (2 * t + 1);
            x.pop_back();
            t += 2;
        } else if (x.empty() || x.back() - t - 1 < a.back()
                   || (x.back() - t - 1 == a.back() && a.back() > t)) {
            if (a.back() <= t)
                break;
            res += a.back() - t;
            a.pop_back();
            t++;
        } else {
            if (x.back() <= 2 * t)
                break;
            res++;
            a.push_back(x.back() - t - 1);
            x.pop_back();
            t++;
        }
    }
    return res;
}

int Test()
{
    int n;
    vector<int> a;
    vector<int> x;
    scanf("%d\n", &n);
    {
        vector<char> s(n + 8);
        fgets(&s[0], n + 8, stdin);
        s.resize(n);
        int cur = 0;
        int b = n;
        for (int i = 0; i < n; ++i) {
           if (s[i] == '1') {
               if (i == cur)
                   b = cur;
               else if (cur != 0)
                   x.push_back(cur);
               cur = 0;
           }
           else
               cur++;
        }
        if (b != 0) a.push_back(b);
        if (cur != 0) a.push_back(cur);
    }
    sort(a.begin(), a.end());
    if (!a.empty() && a.back() == n)
        return 0;
    sort(x.begin(), x.end());
    int res = Count(0, a, x);
    if (!a.empty())
    {
        int a0 = a.back();
        a.pop_back();
        res = max(res, a0 + Count(1, a, x));
        if (!a.empty())
        {
            int a1 = a.back();
            a.pop_back();
            if (a1 > 1)
                res = max(res, a0 + a1 - 1 + Count(2, a, x));
        }
    }
    return n - res;
}

int main()
{
    int t;
    scanf("%d", &t);
    for (; t > 0; t--)
        printf("%d\n", Test());
    return 0;
}