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 <bits/stdc++.h>
using namespace std;
#define ll long long

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int input[n];
    int ile1=0;
    for(int i = 0; i<n;i++){
        input[i] = s[i]-'0';
        if(input[i] == 1){
            ile1++;
        }
    }
    if(ile1 == 0){
        cout << 0 << endl;
        return;
    }
    vector<pair<int, int>> odl(n, {INT_MAX, INT_MAX}); //first -> left second -> right
    queue<int> q;
    for(int i = 0; i<n; i++){
        if(input[i] == 1){
            odl[i] = {0, 0};
            q.push(i);
        }
    }
    while(!q.empty()){
        bool prawodo = true;
        bool lewodo = true;
        int lewo = q.front();
        int prawo = q.front();
        q.pop();
        for(int i = 1; i<n; i++){
            if(!lewodo && !prawodo){
                break;
            }
            if(lewo-i >= 0 && odl[lewo-i].second > i){
                odl[lewo-i].second = i;
            }
            else{
                lewodo = false;
            }
            if(prawo+i < n && odl[prawo+i].first > i){
                odl[prawo+i].first = i;
            }
            else{
                prawodo = false;
            }
        }
    }
    // priority_queue<pair<int, int>> q; //ilemozeuratowac, do kiedy termin
    // priority_queue<pair<int, int>> q2;
    vector<pair<int, int>> licznik;
    vector<pair<int, int>> licznik2;
    //problem there
    for(int i = 0; i<n; i++){
        if(i>0 && i < n-1 && input[i+1] == 0 && input[i-1] == 0){
            continue;
        }
        // if(odl[i].second == INT_MAX && input[i-1] == 0){
        //     continue;
        // }
        // if(odl[i].first == INT_MAX && input[i+1] == 0){
        //     continue;
        // }
        if(odl[i].first == INT_MAX){
            licznik.push_back({i+1, odl[i].second});
        }
        else if(odl[i].second == INT_MAX){
            licznik.push_back({n-i, odl[i].first});
        }
        else{
            licznik2.push_back({max(odl[i].second-1, odl[i].first-1), min(odl[i].second, odl[i].first)});
        }
    }
    sort(licznik.begin(), licznik.end());
    sort(licznik2.begin(), licznik2.end());
    int dzien = 0;
    int saved = 0;
    while(!licznik.empty() && !licznik2.empty()){
        while(!licznik.empty()){
            if(licznik.back().second <= dzien){
                licznik.pop_back();
            }
            else{
                break;
            }
        }
        while(!licznik2.empty()){
            if(licznik2.back().second <= dzien){
                licznik2.pop_back();
            }
            else{
                break;
            }
        }
        if(!licznik.empty() && !licznik2.empty()){
            if(licznik.back().first + licznik[licznik.size()-2].first > licznik2.back().first){
                // cout << licznik.back().first << " " << licznik.back().second << endl;
                dzien++;
                saved += licznik.back().first;
                licznik.pop_back();
            }
            else{
                // cout << licznik2.back().first << " " << licznik2.back().second << endl;
                dzien += 2;
                saved += licznik2.back().first;
                licznik2.pop_back();
            }
        }
        else if(!licznik.empty()){
            // cout << licznik.back().first << " " << licznik.back().second << endl;
            dzien++;
            saved += licznik.back().first;
            licznik.pop_back();
        }
        else if(!licznik2.empty()){
            // cout << licznik2.back().first << " " << licznik2.back().second << endl;
            dzien += 2;
            saved += licznik2.back().first;
            licznik2.pop_back();
        }
    }
    cout << n - saved << endl;


}

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