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

int t, n;
int left_side = 0, right_side = 0;
int buffer[1000007];
bool virus;
string s;

void parse() {
    virus = false;

    for (int i = 0; i <= n; i++) {
        buffer[i] = 0;
    }

    virus = (s.find('1') != string::npos);

    if (!virus) {
        return;
    }

    left_side = s.find_first_of('1');
    right_side = s.size() - s.find_last_of('1') - 1;

    int prev_left, prev_right, next_left, next_right;
    prev_left = s.find_first_of('1');
    prev_right = s.find_last_of('1');
    next_left = s.find_first_of('1', prev_left + 1);
    next_right = s.find_last_of('1', prev_right - 1);

    if (prev_left == prev_right) {
        return;
    }

    while (next_left < next_right) {
        buffer[next_left - prev_left - 1]++;
        buffer[prev_right - next_right - 1]++;

        prev_left = next_left;
        prev_right = next_right;

        next_left = s.find_first_of('1', prev_left + 1);
        next_right = s.find_last_of('1', prev_right - 1);
    }

    if (next_left == next_right) {
        buffer[next_left - prev_left - 1]++;
        buffer[prev_right - next_right - 1]++;
    } else {
        buffer[next_left - next_right - 1]++;
    }

}


int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> t;

    for (int test = 0; test < t; test++) {
        cin >> n >> s;
        parse();

        if (!virus) {
            cout << "0\n";
            continue;
        }

        int survived = 0;
        int time_passed = 0;
        for (int length = n; length > 0; length--) {
            while (buffer[length]) {
                int L_surviving = left_side - time_passed;
                int R_surviving = right_side - time_passed;
                int B_surviving = length - 2 * time_passed;
                if (B_surviving > 1) {
                    B_surviving--;
                }
                if (max({L_surviving, R_surviving, B_surviving}) <= 0) {
                    break;
                }

                if ((L_surviving == R_surviving) && (L_surviving + R_surviving - 1 >= B_surviving) && (L_surviving + R_surviving - 1 > 0)) {
                    survived += L_surviving + R_surviving - 1;
                    left_side = 0;
                    right_side = 0;
                    time_passed += 2;
                    continue;
                }

                if (L_surviving >= B_surviving && L_surviving > 0) {
                    survived += L_surviving;
                    left_side = 0;
                    time_passed++;
                    continue;
                }
                if (R_surviving >= B_surviving && R_surviving > 0) {
                    survived += R_surviving;
                    right_side = 0;
                    time_passed++;
                    continue;
                }
                survived += B_surviving;
                time_passed += (length - 2 * time_passed > 1) ? 2 : 1;
                buffer[length]--;
            }
        }

        if (left_side - time_passed > 0) {
            survived += left_side - time_passed;
            time_passed++;
        }

        if (right_side - time_passed > 0) {
            survived += right_side - time_passed;
            time_passed++;
        }

        cout << n - survived << "\n";
    }
}