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
//
//  main.cpp
//  pan
//
//  Created by Wojciech Siwko on 08/12/2021.
//

#include <iostream>
#include <queue>
#include <tuple>
#include <utility>

using namespace std;

struct Cmp {
    bool operator() (const tuple<int, int, int> &a, const tuple<int, int, int> &b) {
        if (get<0>(a) == get<0>(b)) {
            return get<1>(a) > get<1>(b);
        }
        else return get<0>(a) < get<0>(b);
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t, counter, time, res, b1p, b2p, loss1, loss2;
    int which;
    bool first = true;
    char temp;
    int b, c;
    cin >> t;
    while (t--) {
        counter = 0;
        first = true;
        int n; cin >> n;
        res = n;
        // priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, Cmp> q;
        queue<int> q0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> q1;
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> q2;
        for (int i = 0; i < n; i++) {
            cin >> temp;
            if (temp == '1') {
                if (i != 0) {
                    if (first) {
                        q1.push({counter, 0});
                        first = false;
                    }
                    else q2.push({counter, 0});
                    counter = 0;
                }
                else {
                    first = false;
                }
            }
            else {
                counter++;
            }
        }
        if (counter != 0) {
            if (q1.empty() && q2.empty()) q0.push(counter);
            else q1.push({counter, 0});
        }
        
        time = 0;
        while (!q1.empty() || !q2.empty()) {
            if (!q1.empty() && !q2.empty()) {
                auto [b1, c1] = q1.top();
                auto [b2, c2] = q2.top();
                b1p = b1 - (time - c1);
                b2p = b2 - (time - c2)*2;
                if (b1p <= 0 && b2p <= 0) {q1.pop(); q2.pop(); continue;}
                else if (b1p <= 0) {
                    b = b2p; c = c2; q2.pop(); which = 2;
                    goto skip;
                }
                else if (b2p <= 0) {
                    b = b1p; c = c1; q1.pop(); which = 1;
                    goto skip;
                }
                loss1 = 0;
                loss2 = 0;
                if (b2p >= 2) {loss2 += 1; loss1 += 2;}
                else if (b2p == 1) loss1 += 1;
                if (b1p >= 2) loss2 += 2;
                else if (b1p == 1) loss2 += 1;
                loss1 -= b1p;
                loss2 -= (b2p - 1);
                if (loss1 == loss2 || loss2 > loss1) {
                    b = b1p; c = c1; q1.pop(); which = 1;
                } else {
                    b = b2p; c = c2; q2.pop(); which = 2;
                }
            } else if (!q1.empty()) {
                auto [b1, c1] = q1.top();
                b1p = b1 - (time - c1);
                if (b1p > 0) {b = b1p; c = c1; q1.pop(); which = 1;}
                else {q1.pop(); continue;}
            } else {
                auto [b2, c2] = q2.top();
                b2p = b2 - (time - c2)*2;
                if (b2p > 0) {b = b2p; c = c2; q2.pop(); which = 2;}
                else {q2.pop(); continue;}
            }
            skip:
            if (which == 1) {
                q0.push(b - 1); res--; time++;
            }
            else {
                q1.push({b - 1, time}); res--; time++;
            }
        }
        
        while (!q0.empty()) {
            res -= q0.front();
            q0.pop();
        }
        
        cout << res << endl;
    }
    return 0;
}