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


using namespace std;


int solveRec(int iOnes, int iTwos, int timeSoFar, vector <int> &indOnes, vector <int> &indTwos, const vector <pair<int,int>> &gaps) {
    int nOnes = indOnes.size(), nTwos = indTwos.size();

    if (iOnes < nOnes && gaps[indOnes[iOnes]].first <= timeSoFar) iOnes = nOnes;
    if (iTwos < nTwos && gaps[indTwos[iTwos]].first <= 2 * timeSoFar) iTwos = nTwos;

    if (iOnes == nOnes && iTwos == nTwos) {
        return 0;
    }

    bool tryOne, tryTwo;
    if (iOnes == nOnes) {
        tryOne = false, tryTwo = true;
    } else if (iTwos == nTwos) {
        tryOne = true, tryTwo = false;
    } else {
        int gainOne = gaps[indOnes[iOnes]].first - timeSoFar;
        int valueTwo = gaps[indTwos[iTwos]].first - 2 * timeSoFar;
        int gainTwo = valueTwo - (valueTwo >= 2);

        tryOne = gainOne >= gainTwo || gainOne <= 3;
        tryTwo = gainTwo > gainOne;
    }

    int ans = 0;

    if (tryOne) {
        int fst = gaps[indOnes[iOnes]].first - timeSoFar;
        ans = max(
            ans,
            fst + solveRec(iOnes + 1, iTwos, timeSoFar + 1, indOnes, indTwos, gaps)
        );
    }

    if (tryTwo) {
        int fst = gaps[indTwos[iTwos]].first - 2 * timeSoFar;
        ans = max(
            ans,
            fst - (fst >= 2) + solveRec(iOnes, iTwos + 1, timeSoFar + (fst >= 3 ? 2 : 1), indOnes, indTwos, gaps)
        );
    }

    return ans;
}

int solveGaps(vector <pair<int,int>> &gaps) {
    vector <int> indOnes, indTwos;
    for (int i = 0; i < (int) gaps.size(); i++) {
        if (gaps[i].second == 1) {
            indOnes.push_back(i);
        } else {
            indTwos.push_back(i);
        }
    }

    sort(indOnes.begin(), indOnes.end(), [&](int i, int j) {
        return gaps[i].first > gaps[j].first;
    });

    sort(indTwos.begin(), indTwos.end(), [&](int i, int j) {
        return gaps[i].first > gaps[j].first;
    });

    int timeSoFar = 0;
    return solveRec(0, 0, timeSoFar, indOnes, indTwos, gaps);
}

int solve(int n, const string &s) {
    vector <pair<int,int>> gaps;
    for (int l = 0; l < n; l++) if (s[l] == '0') {
        int r = l;
        while (r < n - 1 && s[r + 1] == '0') {
            r++;
        }

        if (l == 0 && r == n - 1) {
            return 0;
        } else {
            gaps.push_back({r - l + 1, (l != 0) + (r != n - 1)});
        }

        l = r;
    }

    if (gaps.empty()) {
        return n;
    }

    return n - solveGaps(gaps);
}

int main() {
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        string s;
        cin >> s;

        cout << solve(n, s) << '\n';
    }

    return 0;
}