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

using namespace std;

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;

    vector<int> seg;
    int act = 0;
    for (int i = 0; i < n; i++){
        if (s[i] == '1')
            continue;
        act = 0;
        while (i < n && s[i] == '0'){
            i++;
            act++;
        }
        seg.push_back(act);
    }

    if (seg.size() <= 1){
        cout << n - act << "\n";
        return;
    }

    vector<int> edges;
    if (s.back() == '0'){
        edges.push_back(seg.back());
        seg.pop_back();
    }

    if (s[0] == '0'){
        edges.push_back(seg[0]);
        seg[0] = seg.back();
        seg.pop_back();
    }

    sort(seg.begin(), seg.end(), greater<int>());
    sort(edges.begin(), edges.end(), greater<int>());

    int rescue = 0;
    for (int t = 0, s_id = 0, e_id = 0; true; t++){
        int add = 0;
        if (s_id < (int)seg.size() && e_id < (int)edges.size()){
            if (seg[s_id]-2*t == 1 && 1 > edges[e_id]-t){
                rescue++;
                break;
            }

            int s_add = seg[s_id]-1-2*t, e_add = edges[e_id]-t;
            if (s_add/2 >= e_add){
                add = s_add;
                s_id++;
                t++;
            }
            else{
                add = e_add;
                e_id++;
            }
        }
        else if (s_id < (int)seg.size()){
            if (seg[s_id]-2*t == 1){
                rescue++;
                break;
            }
            add = seg[s_id]-1-2*t;
            s_id++;
            t++;
        }
        else if (e_id < (int)edges.size()){
            add = edges[e_id]-t;
            e_id++; 
        }
        else{
            break;
        }

        if (add <= 0)
            break;
        
        rescue += add;
    }

    cout << n - rescue << "\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t){
        solve();
        t--;
    }
}

/*
1
1000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000010000000000000000000000000000000000011

*/