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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    std::ios::sync_with_stdio(false);

    int t, n, len, res, time;
    string s;
    vector<int> v;
    vector<pair<int, int>> lens_of_intervals;

    cin >> t;

    for (auto k = 0; k < t; k++) {
        cin >> n;
        cin >> s;
        len = 0;
        res = 0;

        for (auto i = 1; i < n; i++) {
            len++;
            if (s[i] != s[i - 1]) {
                if (s[i - 1] == '0') {
                    v.push_back(len);
                }

                len = 0;
            }
        }

        if (s[n - 1] == '0') {
            v.push_back(len + 1);
        }

        if (v[0] == n) {
            if (s[0] == '0') {
                printf("0\n");
            } else {
                printf("%d\n", n);
            }
        } else {
            for (auto i = 0; i < v.size(); i++) {
                if ((i == 0 && s[0] == '0') || (i == v.size() - 1 && s[n - 1] == '0')) {
                    lens_of_intervals.emplace_back(make_pair(v[i] * 2, 2)); // one border
                } else {
                    lens_of_intervals.emplace_back(make_pair(v[i], 1));
                }
            }

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

            time = 0;

            for (int i = lens_of_intervals.size() - 1; i >= 0; i--) {
                if (lens_of_intervals[i].second == 2) {
                    res += max(0, lens_of_intervals[i].first / 2 - time);
                    time++;
                } else {
                    res += max(0, lens_of_intervals[i].first - 1 - 2 * time);
                    time += 2;
                }
            }

            printf("%d\n", n - res);
        }

        v.clear();
        lens_of_intervals.clear();
    }


    return 0;
}