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

using namespace std;

struct Island
{
    Island(int s, int hc) : size(s), half_closed(hc) {}
    int size;
    int half_closed;
    bool operator<(const Island &rhs)
    {
        return size + half_closed > rhs.size + rhs.half_closed;
    }
};

ostream &operator<<(ostream &o, const Island &v)
{
    return o << v.size << ", " << (v.half_closed ? "half closed" : "open");
}

void deathjab(int n, const string &bytia)
{
    if (count(bytia.begin(), bytia.end(), '1') == 0)
    {
        cout << 0 << endl;
        return;
    }

    vector<Island> islands;

    int half_closed = (bytia[0] == '0');
    int begin_zeros = 0;

    for (int i = 1; i < n; ++i)
    {
        if (bytia[i - 1] == '1' && bytia[i] == '0')
        {
            begin_zeros = i;
            continue;
        }
        if (bytia[i - 1] == '0' && bytia[i] == '1')
        {
            islands.emplace_back(i - begin_zeros, half_closed);
            // cout << "Island: " << islands.back() << endl;
            half_closed = 0;
        }
    }
    if (bytia[n - 1] == '0')
    {
        islands.emplace_back(n - begin_zeros, 1);
        // cout << "Island: " << islands.back() << endl;
    }

    sort(islands.begin(), islands.end());

    int saved = 0;
    int age = 0;
    for (Island &i : islands)
    {
        int remaining = i.size - age * (2 - i.half_closed) - 1 + i.half_closed;
        // cout << i << ", remaining: " << remaining << endl;
        if (remaining < 0)
            break;
        saved += remaining;
        age += (2 - i.half_closed);
    }
    cout << (n - saved) << endl;
}

int main()
{
    int t, n;
    string bytia;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        cin >> n >> bytia;
        // cout << bytia << endl;
        deathjab(n, bytia);
    }
    return 0;
}