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
#include <iostream>
#include <set>
#include <string>
#include <functional>

using namespace std;

// #define USE_CERR_LOG

#ifdef USE_CERR_LOG
#define LOG if (true) cerr
#else
#define LOG if (false) cerr
#endif

void log(const multiset<int, greater<int>>& block, string prefix) {
#ifdef USE_CERR_LOG    
    cerr << prefix << ": ";
    for (int elem : block) {
        cerr << elem << ' ';
    }
    cerr << endl;
#endif    
}

int solve(const string& cities) {
    multiset<int, greater<int>> oneSided, twoSided;
    int cityCount = cities.length();
    int zeroStart = -1;
    int i;

    for (i = 0; i < cityCount && cities[i] == '0'; i++) {}
    if (i > 0) {
        oneSided.insert(i);
        if (i == cityCount) return 0;
    }
    for (; i < cityCount; i++) {
        if (zeroStart == -1 && cities[i] == '0') { zeroStart = i; }
        else if (zeroStart > 0 && cities[i] == '1') {
            twoSided.insert(i - zeroStart);
            zeroStart = -1;
        }
    }
    if (zeroStart >= 0) { oneSided.insert(cityCount - zeroStart); }
    if (oneSided.empty() && twoSided.empty()) { return cityCount; }

    int result = 0;
    
    for (int clock = 1; !oneSided.empty() || !twoSided.empty(); clock ++) {
        // LOG << clock << ": " << result << " - ";
        // log(oneSided, "one");
        // log(twoSided, "two");
        
        if (oneSided.empty()) {
            auto twoIt = twoSided.begin();
            int left = *twoIt - 2 * (clock - 1);
            twoSided.erase(twoIt);
            if (left > 1) { oneSided.insert(left - 1 + clock); }
            else if (left == 1) { result += 1; }
            else { break; }
        } else if (twoSided.empty()) {
            auto oneIt = oneSided.begin();
            int left = *oneIt - clock + 1;
            oneSided.erase(oneIt);
            if (left > 0) { result += left; }
            else { break; }
        } else {
            auto oneIt = oneSided.begin();
            auto twoIt = twoSided.begin();
            int oneLeft = *oneIt - clock + 1;
            int twoLeft = *twoIt - 2*clock + 2;
            if (oneLeft > 0 && (oneLeft+2 >= twoLeft)) {
                result += oneLeft;
                oneSided.erase(oneIt);
            } else if (twoLeft > 0) {
                twoSided.erase(twoIt);
                if (twoLeft == 1) { result += 1; }
                else { oneSided.insert(twoLeft - 1 + clock); }
            } else {
                break;
            }
        }
    }

    return cityCount - result;
}

int main() {
    ios_base::sync_with_stdio(false);
    int setCount, cityCount;
    string cities;

    cin >> setCount;
    while (setCount --) {
        cin >> cityCount >> cities;
        cout << solve(cities) << endl;
    }

    return 0;
}