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

using namespace std;

#define st first
#define nd second
#define PII pair <int, int>

const int N = 100'007;

int n;
char buf[N];

int get_ans(vector <PII> &intervals) 
{
    sort(intervals.begin(), intervals.end(), 
        [](const PII &a, const PII &b) {
            return 2 * a.st * a.nd + a.nd > 2 * b.st * b.nd + b.nd;
        }
    );

    int days_passed = 0, ret = 0;
    for (const auto &[len, type]: intervals) {
        int cur_len = len;
        if (type == 1) {
            cur_len -= 2 * days_passed;
        } else {
            cur_len -= days_passed;
        }

        if (cur_len <= 0)
            break;
        
        if (type == 1) {
            if (cur_len <= 2) {
                days_passed += 1;
                ret += 1;
            } else {
                days_passed += 2;
                ret += cur_len - 1;
            }
        } else {
            ret += cur_len;
            days_passed += 1;
        }
    }

    return ret;
}

void solve() 
{
    scanf("%d", &n);
    scanf("%s", buf + 1);

    int left = -1, right = n + 1;
    for (int i = 1; i <= n; ++i) {
        if (buf[i] == '0') {
            continue;
        }
        
        right = i;
        if (left == -1) {
            left = i;
        }
    }

    if (left == -1) {
        puts("0");
        return;
    }

    int last = left;
    vector <PII> free_intervals;

    for (int i = left + 1; i <= right; ++i) {
        if (buf[i] == '0') {
            continue;
        }

        if (last + 1 < i) {
            free_intervals.push_back({i - last - 1, 1});
        }

        last = i;
    }

    if (left > 1) {
        free_intervals.push_back({left - 1, 2});
    }

    if (right < n) {
        free_intervals.push_back({n - right, 2});
    }

    int ans = get_ans(free_intervals);
    printf("%d\n", n - ans);
}

int main()
{
    int cases;
    scanf("%d", &cases);

    while (cases--) {
        solve();
    }
}