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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>

using namespace std;

vector<int> lens;
vector<pair<int, int>> segments;

bool custom_cmp(pair<int, int> x, pair<int, int> y) {
    int a = x.first/x.second*x.second;
    int b = y.first/y.second*y.second;

    if(a*y.second == b*x.second) {
        return x.first > y.first;
    }
    return a*y.second < b*x.second;
}

int main() {
    // cout << custom_cmp({5, -2}, {3, -1}) << endl;
    // return 0;

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while(t--) {
        lens.clear();
        segments.clear();

        int n;
        cin >> n;
        string s;
        cin >> s;
        // cout << s << endl;

        int i = 0;
        int infected = 0;
        while(i < n) {
            int len = 0;
            while(i < n && s[i] == '0') {
                len++;
                i++;
            }
            while(i < n && s[i] == '1') {
                infected++;
                i++;
            }
            if(len) {
                lens.push_back(len);
            }
        }

        if(lens.size() == 0) {
            cout << infected << "\n";
            continue;
        }

        // for(auto x: lens) {
        //     cout << x << " ";
        // }
        // cout << endl;

        for(auto x: lens) {
            segments.push_back({x, -2});
        }

        if(s[0] == '0') {
            segments[0].second++;
        }

        if(s.back() == '0') {
            segments.back().second++;
        }

        // cout << segments.size() << endl;

        sort(segments.begin(), segments.end(), custom_cmp);
        // reverse(segments.begin(), segments.end());

        // for(auto x: segments) {
        //     cout << x.first << " " << x.second << endl;
        // }
        // cout << endl;

        // for(auto x: segments) {
        //     cout << x.first << " " << x.second << endl;
        // }
        
        // int days = 0;
        // for(auto seg: segments) {
        //     cout << "d: " << days << endl;
        //     int last_days = 0;
        //     while(seg.second && seg.first) {
        //         int m = min(seg.first, -(days - last_days)*seg.second);
        //         infected += m;
        //         cout << m << endl;
        //         seg.first -= m;
        //         if(seg.first) {
        //             seg.first--;
        //         }

        //         seg.second++;
        //         last_days = days;
        //         days++;
        //     }
        // }

        int days = 0;
        for(auto seg: segments) {
            // cout << "days: " << days << endl;
            int m = min(seg.first, -days*seg.second);
            // cout << "m: " << m << endl;
            infected += m;
            seg.first -= m;

            while(seg.first && seg.second) {
                // cout << seg.first << " " << seg.second << endl;
                if(seg.first) {
                    seg.first--;
                    seg.second++;
                }

                // cout << seg.first << " " << seg.second << endl;
                if(seg.first) {
                    seg.first += seg.second;
                    infected -= seg.second;
                }
                days++;
            }
        }


        // return 0;

        cout << infected << "\n";
        // cout << endl;
    }

    return 0;
}