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
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int maxN = 1e5 + 10;

struct Hole {
    int x, l;

    Hole(int x, int l) : x(x), l(l) {}
    bool operator<(Hole const &o) const { return l > o.l; }
};

vector<Hole> holes;
char t[maxN];
int N;

int moves_done;

int del(Hole &hole) {
    if (hole.l <= 2 * moves_done)
        return 0;
    moves_done++;
    if (hole.x == 1 || hole.x + hole.l - 1 > N)
        return hole.l / 2 - moves_done + 1;
    // reality
    hole.l -= 2 * moves_done - 2;
    if (hole.l == 1)
        return 1;
    moves_done++;
    return hole.l - 1;
}

bool get_input() {
    scanf("%d%s", &N, t + 1);
    t[N + 1] = t[0] = 'x';
    t[N + 2] = 0;

    for (int i = 1; i <= N; ++i)
        if (t[i] == '1')
            return true;
    return false;
}

void create_hole(int a, int b) {
    int len = b - a + 1;
    if (a == 1 || b == N)
        len *= 2;
    // printf("HOLE %d-%d -> %d\n", a, b, len);
    holes.emplace_back(a, len);
}

void get_holes() {
    int last0 = -1;
    for (int i = 1; i <= N + 1; ++i) {
        if (t[i] == '0') {
            if (last0 == -1)
                last0 = i;
        } else {
            if (last0 != -1)
                create_hole(last0, i - 1);
            last0 = -1;
        }
    }
}


void prog() {
    if (!get_input()) {
        puts("0");
        return;
    }
    holes.clear();
    get_holes();
    sort(holes.begin(), holes.end());
    int hp = 0;
    moves_done = 0;
    for (Hole &hole : holes)
        hp += del(hole);
    printf("%d\n", N - hp);
}


int main() {
    int _;
    scanf("%d", &_);
    while (_--)
        prog();
}