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

struct zeros
{
    int count;
    int time;
    int time_left;

    zeros(int count, int time) : count(count), time(time), time_left(count/time) { }

    bool operator<(const zeros& other) const
    {
        return time_left > other.time_left;
    }
};

int compute_saved(const std::vector<int>& single_zeros, const std::vector<int>& double_zeros, int single_with_priority)
{
    int time = 0;
    int saved = 0;

    auto single_it = single_zeros.begin(), double_it = double_zeros.begin();
    int best_single, best_double;
    while (
            best_single = (single_it != single_zeros.end()) ? std::max(0,*single_it-time) : 0,
                    best_double = (double_it != double_zeros.end()) ? std::max(0,*double_it-2*time) : 0,
                    best_single || best_double
            ) {
        bool use_single = false;
        if (!best_single) {
            use_single = false;
        } else if (!best_double) {
            use_single = true;
        } else if (single_with_priority) {
            use_single = true;
            single_with_priority--;
        }
        if (use_single) {
            saved += best_single;
            time++;
            ++single_it;
        } else {
            if (best_double > 2) {
                saved += best_double - 1;
                time += 2;
            } else {
                ++saved;
                ++time;
            }
            ++double_it;
        }
    }
    return saved;
}

int main()
{
    std::vector<int> single_zeros;
    std::vector<int> double_zeros;
    single_zeros.reserve(2);
    double_zeros.reserve(100000);

    int T;
    scanf("%d\n", &T);
    while (T--) {
        single_zeros.clear();
        double_zeros.clear();

        int N;
        scanf("%d\n", &N);
        int i_last_one = 0;
        int i_first_one = 0;
        for (int i=1; i<=N; ++i) {
            if (getchar() == '1') {
                if (i_last_one > 0) {
                    int count = i - i_last_one - 1;
                    if (count > 0) {
                        double_zeros.push_back(count);
                    }
                }
                i_last_one = i;
                if (!i_first_one) {
                    i_first_one = i;
                }
            }
        }
        if (!i_last_one) {
            puts("0");
            continue;
        }
        if (i_first_one > 1) {
            single_zeros.push_back(i_first_one - 1);
        }
        if (i_last_one < N) {
            single_zeros.push_back(N - i_last_one);
        }

        std::sort(single_zeros.begin(), single_zeros.end(), std::greater<int>());
        std::sort(double_zeros.begin(), double_zeros.end(), std::greater<int>());

        int saved = std::max(
            compute_saved(single_zeros, double_zeros, 0),
            std::max(
                compute_saved(single_zeros, double_zeros, 1),
                compute_saved(single_zeros, double_zeros, 2)
            )
        );
        printf("%d\n", N - saved);
    }
}