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

using namespace  std;

using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pair<int, int>>;

void print_int_vec(vi const &v) {
    for(auto el: v) {
        cout << el << ", ";
    }
    cout << endl;
}

void print_pii_vec(vpi const &v) {
    for(auto [f, s] : v) {
        cout << "<" << f << ", " << s << "> ; ";
    }
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    for (int i_t = 0; i_t < t; ++i_t) {
        int n;
        cin >> n;
        vi sick_mask(n);
        for (int i = 0; i < n; ++i) {
            char d;
            cin >> d;
            sick_mask[i] = d - '0';
        }

        vi days_till_dead(n, INT32_MAX);
        int counter = 0;
        bool any_sick = false;
        for (int i = 0; i < n; ++i) {
            if(sick_mask[i]) {
                any_sick = true;
                counter = 0;
            }
            if(any_sick) {
                days_till_dead[i] = counter;
            }
            counter++;
        }
        any_sick = false;
        for (int i = n-1; i >= 0; i--) {
            if(sick_mask[i]) {
                any_sick = true;
                counter = 0;
            }
            if(any_sick) {
                days_till_dead[i] = min(days_till_dead[i], counter);
            }
            counter++;
        }

        vpi clusters;
        int count = 0;
        int time = 0;
        for (int i = 0; i < n; ++i) {
            if(sick_mask[i]) {
                if(count > 0) {
                    clusters.push_back({count, time});
                }
                count = 0;
                time = 0;
            }
            else {
                count += 1;
                time = max(time, days_till_dead[i]);
            }
        }
        if(count > 0) {
            clusters.push_back({count, time});
        }

        sort(clusters.begin(), clusters.end(), [](auto a, auto b) {return a.second > b.second || (a.second == b.second && a.first > b.first);});

//        cout << endl;
//        print_int_vec(sick_mask);
//        print_int_vec(days_till_dead);
//        print_pii_vec(clusters);
        int saved = 0;
        int days_gone = 0;

        for(auto [count, time] : clusters) {
            if (days_gone >= time) break;
            if((count + 1) / 2 == time) {
                int new_saved = count - 1 - (days_gone * 2);
                if(new_saved == 1) {
                    days_gone += 1;
                }
                else {
                    days_gone += 2;
                }
                saved += new_saved;
            }
            else {
                // single
                int new_saved = count - days_gone;
                saved += new_saved;
                days_gone += 1;
            }
        }
        cout << n - saved << "\n" ;
    }
    return 0;
}