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

using namespace std;

#define pb push_back
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define mp make_pair
#define fi first
#define se second
#define PII pair<int,int>
#define vPII vector<PII>

int t, n;
string s;

// 00000000010000000000100000000000000000000000001000000000000000000000000000000000000000001
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        vPII v;
        int sick = 0;
        cin >> n >> s;
        s.append("1");
        int buf = 0;
        for (char i : s) {
            if (i == '1') {
                if (buf > 0) {
                    v.push_back(make_pair(buf, 0));
                    buf = 0;
                }
                sick++;
            }
            else buf += 1;
        }
        sick--;
        if (s[0] == '0') v[0].second = 1;
        if (s[n-1] == '0') v.back().second = 1;
        sort(v.begin(), v.end(), [v](PII x, PII y) {return x.first + x.second * 2 > y.first + y.second * 2;});
        int all;
        while(!v.empty()) {
            all = 0;
            for (int i = 0; i < v.size(); i++) { // vax first unvaxxed cluster
                if (v[i].second == 2 || v[i].first == 0) all++;
                else {
                    if (v[i].first == 1) v[i].second = 2;
                    else v[i].second += 1;
                    break;
                }
            }
            if (all == v.size()) break;
            else { // spread the virus
                for (int i = v.size() - 1; i >= all; i--) {
                    if (v[i].first == 0) {
                        if (v.size() == i+1) v.pop_back();
                        continue;
                    }
                    else if ((v[i].second == 1) || (v[i].first == 1 && v[i].second == 0)){
                        v[i].first -= 1;
                        sick++;
                    }
                    else if (v[i].second == 0) {
                        v[i].first -= 2;
                        sick += 2;
                    }
                }
            }
        }
        cout << sick << '\n';
    }
}