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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdio>
#include <vector>
#include <algorithm>

const int DEBUG = 0;

void read_segments(int n, std::vector<int> &segments, std::vector<int> &ends) {
    int bits = 0;
    char c;
    for (int i = 0; i < n; ++i) {
        scanf("%c", &c);
        if (c == '0') {
            ++bits;
        } else {
            if (bits == i && i > 0) {
                ends.push_back(bits);
            } else {
                if (DEBUG) printf("bits %d\n", bits);
                segments.push_back(bits);
            }
            bits = 0;
        }
    }
    scanf("%c", &c); // endl
    if (bits > 0)
        ends.push_back(bits);
}

int take_segment(std::vector<int> &segments, int &day) 
{
    if (segments.empty())
        return 0;
    int q = segments.back() - 2 * day;
    if (q > 1) {
        q--;
        day++;
    }
    day++;
    segments.pop_back();
    return q;
}

int take_end(std::vector<int> &ends, int &day) 
{
    if (ends.empty())
        return 0;
    int q = ends.back() - day;
    if (q > 0) {
        day++;
        ends.pop_back();
    }

    return q;
}

int main() {

    int t;
    scanf("%d", &t);

    while (t--) {

        int n;
        scanf("%d\n", &n);

        std::vector<int> segments;
        std::vector<int> ends;
        read_segments(n, segments, ends);

        std::sort(segments.begin(), segments.end(), std::greater<int>());
        while (!segments.empty() && (segments.back() < (segments.size()-1) * 2))
            segments.pop_back();
        std::reverse(segments.begin(), segments.end());

        std::sort(ends.begin(), ends.end());

        if (DEBUG && ends.size() > 0) printf("begin %d\n", ends.back());
        if (DEBUG && ends.size() > 1) printf("end %d\n", ends[1]);

        int day = 0;
        int vaccinated = 0;

        while (!segments.empty() && segments.back() - 2*day > 5) {
            int s = segments.back();
            int q = take_segment(segments, day);
            if (DEBUG) printf("vaccine(segment) it = %d q = %d\n", s, q);
            vaccinated += q;
        }

        while (!ends.empty() && ends.back() - day >= 3) {
            int s = ends.back();
            int q = take_end(ends, day);
            if (DEBUG) printf("vaccine(end) %d q = %d\n", s, q);
            vaccinated += q;
        }

        while (!segments.empty() && segments.back() - 2*day >= 5) {
            int s = segments.back();
            int q = take_segment(segments, day);
            if (DEBUG) printf("vaccine(segment) it = %d q = %d\n", s, q);
            vaccinated += q;
        }

        while (!ends.empty() && ends.back() - day >= 2) {
            int s = ends.back();
            int q = take_end(ends, day);
            if (DEBUG) printf("vaccine(end) %d q = %d\n", s, q);
            vaccinated += q;
        }

        while (!segments.empty() && segments.back() - 2*day >= 3) {
            int s = segments.back();
            int q = take_segment(segments, day);
            if (DEBUG) printf("vaccine(segment) it = %d q = %d\n", s, q);
            vaccinated += q;
        }

        while (!ends.empty() && ends.back() - day >= 1) {
            int s = ends.back();
            int q = take_end(ends, day);
            if (DEBUG) printf("vaccine(end) %d q = %d\n", s, q);
            vaccinated += q;
        }

        while (!segments.empty() && segments.back() - 2*day >= 1) {
            int s = segments.back();
            int q = take_segment(segments, day);
            if (DEBUG) printf("vaccine(segment) it = %d q = %d\n", s, q);
            vaccinated += q;
        }

        printf("%d\n", n - vaccinated);
    }

    return 0;
}