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

using namespace std;

int OBLICZ(int LL, int PP, vector<int> KRAJ) { // LL >= PP
    int w1 = 1000000, w2 = 1000000;

    if (KRAJ.size() > 0 && KRAJ[0] > 2) {
        vector<int> tmp = KRAJ;
        tmp[0] = 0;
        w1 = 1;
        for (size_t i = 1; i < tmp.size(); i++) {
            if (tmp[i] >= 4) {
                w1 += 4;
                tmp[i] -= 4;
            }
            else {
                w1 += tmp[i];
                tmp[i] = 0;
            }
        }
        while (tmp.size() > 0 && tmp[tmp.size() - 1] == 0) tmp.pop_back();
        if (tmp.size() > 1) swap(tmp[0], tmp[tmp.size() - 1]);
        while (tmp.size() > 0 && tmp[tmp.size() - 1] == 0) tmp.pop_back();
        int ll = LL, pp = PP;
        if (ll >= 2) {
            w1 += 2;
            ll -= 2;
        }
        else {
            w1 += ll;
            ll = 0;
        }
        if (pp >= 2) {
            w1 += 2;
            pp -= 2;
        }
        else {
            w1 += pp;
            pp = 0;
        }
        if (tmp.size() > 0 || ll > 0) {
            w1 += OBLICZ(ll, pp, tmp);
        }
    } else if (KRAJ.size() > 0 && KRAJ[0] > 0) {
        vector<int> tmp = KRAJ;
        if (tmp[0] > 1) w1 = 1;
        else w1 = 0;
        tmp[0] = 0;
        for (size_t i = 1; i < tmp.size(); i++) {
            w1 += tmp[i];
            tmp[i] = 0;
        }
        while (tmp.size() > 0 && tmp[tmp.size() - 1] == 0) tmp.pop_back();
        if (tmp.size() > 1) swap(tmp[0], tmp[tmp.size() - 1]);
        while (tmp.size() > 0 && tmp[tmp.size() - 1] == 0) tmp.pop_back();
        int ll = LL, pp = PP;
        if (ll >= 1) {
            w1 += 1;
            ll -= 1;
        }
        if (pp >= 1) {
            w1 += 1;
            pp -= 1;
        }
        if (tmp.size() > 0 || ll > 0) {
            w1 += OBLICZ(ll, pp, tmp);
        }
    }


    if (LL > 0) {
        vector<int> tmp = KRAJ;
        w2 = 0;
        for (size_t i = 0; i < tmp.size(); i++) {
            if (tmp[i] >= 2) {
                w2 += 2;
                tmp[i] -= 2;
            }
            else {
                w2 += tmp[i];
                tmp[i] = 0;
            }
        }
        while (tmp.size() > 0 && tmp[tmp.size() - 1] == 0) tmp.pop_back();
        int pp = PP;
        if (pp >= 1) {
            w2 += 1;
            pp -= 1;
        }
        if (tmp.size() > 0 || pp > 0) {
            w2 += OBLICZ(pp, 0, tmp);
        }
    }
    if (w1 > w2) return w2;
    else return w1;
}

int main() {
    int t;
    cin >> t;
    for (int r = 0; r < t; r++) {
        int n;
        vector<int> KRAJ = {};
        string DANE;
        int i = 0, odp = 0, LL = 0, PP = 0;

        cin >> n;
        cin >> DANE;

        while (DANE[i] == '0' && i < n) { // zaczęło się od 0
            LL++;
            i++;
        }
        while (DANE[i] == '1' && i < n) { // pierwszy fragment pandemiczny
            odp++;
            i++;
        }
        int M = 0;
        while (i < n) {
            if (DANE[i] == '0') M++;
            else {
                if (M > 0) KRAJ.push_back(M);
                M = 0;
                odp++;
            }
            i++;
        }
        PP = M;

        if (LL < PP) swap(LL, PP);

        if (KRAJ.size() > 1) sort(KRAJ.begin(), KRAJ.end(), greater<>());

        if (odp == n) cout << odp << endl;
        else cout << odp + OBLICZ(LL, PP, KRAJ) << endl;
    }
    return 0;
}