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

using namespace std;

void solve(vector<int>& v) {
    vector<int> inner_blocks;
    int left_border = 0;
    int right_border = 0;

    // Parse 0..0 blocks
    int i = 0;
    for (;;) {
        while (i < v.size() && v[i] == 1) i++;
        int start = i;
        while (i < v.size() && v[i] == 0) i++;
        int end = i;
        //cout << start << ", " << end << endl;
        if (start < v.size()) {
            if (start == 0) {
                left_border = end - start;
            } else if (end == v.size() && start != 0) {
                right_border = end - start;
            } else {
                inner_blocks.push_back(end - start);
            }
        }
        if (i >= v.size()) {
            break;
        }
    }

    sort(inner_blocks.begin(), inner_blocks.end(), greater<int>());

    /*for (auto a : inner_blocks) {
        cout << a << " ";
    }
    cout << endl;
    cout << "left_border: " << left_border << ", right_border: " << right_border << endl;*/

    int saved_count = 0;
    int time = 0;
    int inner_block_idx = 0;
    for (;;) {
        // pick
        int inner_block_value = inner_block_idx < inner_blocks.size() ? inner_blocks[inner_block_idx] - 2 * time : 0;  
        if (inner_block_value < 0) {
            inner_block_value = 0;
        }  
        int left_border_value = left_border - time;
        if (left_border_value < 0) {
            left_border_value = 0;
            left_border = 0;
        }
        int right_border_value = right_border - time;
        if (right_border_value < 0) {
            right_border_value = 0;
            right_border = 0;
        }

        if ((left_border_value == 2 && inner_block_value == 3) || (left_border_value > 0 && left_border_value >= right_border_value && left_border_value >= inner_block_value)) {
            saved_count += left_border_value;
            left_border = 0;
            time++;
            //cout << "c1 " << left_border_value << endl;
        } else if ((right_border_value == 2 && inner_block_value == 3) || (right_border_value > 0 && right_border_value >= left_border_value && right_border_value >= inner_block_value)) {
            saved_count += right_border_value;
            right_border = 0;
            time++;
            //cout << "c2 " << right_border_value << endl;
        } else {
            if (inner_block_value > 2) {
                saved_count += (inner_block_value - 1);
                time += 2;
            } else if (inner_block_value == 1 || inner_block_value == 2) {
                saved_count++;
                time++;
            } else {
                time++;
            }
            inner_block_idx++;
            //cout << "c3 " << inner_block_value << endl;;
        }

        // end condition
        //cout << inner_block_idx << ", " << inner_blocks.size() << ", " << left_border << ", " << right_border << endl;
        if (inner_block_idx >= inner_blocks.size() && left_border == 0 && right_border == 0) {
            break;
        }
    }

    //cout << "v.size = " << v.size() << ", saved_count = " << saved_count << endl;
    cout << (v.size() - saved_count) << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 0;
    int n = 0;
    char c;

    cin >> t;

    for (int i = 0; i < t; i++) {
        cin >> n;
        vector<int> v(n, 0);
        for (int j = 0; j < n; j++) {
            cin >> c;
            if (c == '0') {
                v[j] = 0;
            } else {
                v[j] = 1;;
            }
        }
        solve(v);
    }

    return 0;
}