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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


int main(){
    int t;
    cin >> t;
    while(t--){
        bool cc=false;
        int n;
        cin >> n;
        vector<int> v;
        vector<int> v2;
        for(int i=0;i<n;){
            char c;
            cin >> c;
            if(c=='0'){
                int holes = 2;
                int curr_i = i;
                while(c=='0'){
                    i++;
                    if(i==n){
                        i++;
                        break;
                    }
                    cin >> c;
                }
                if(c=='1'){
                    i++;
                }
                if(curr_i == 0){
                    holes--;
                }
                if(i==n+1){
                    holes--;
                }
                if(holes==1){
                    v2.push_back(i-curr_i-1);
                }else if(holes==2){
                    v.push_back(i-curr_i-1);
                }else{
                    cc = true;
                    cout << 0 << endl;
                }
            }else{
                i++;
            }
        }
        sort(v.begin(),v.end(), greater<int>());
        sort(v2.begin(),v2.end(), greater<int>());
        int time = 0;
        int score = 0;
        if(v.empty()&&v2.size()==2){
            cout << n- (v2[0]+v2[1]-1) << endl;
        }
        if(v.empty()&&v2.size()==1){
            cout << n-v2[0] << endl;
        }
        for(int i=0;i<v.size();i++){
            if(v2.size()!=0){
                if(v2[0]-time>=v[i]-2*time-2 && v2[0]>time){
                    if(v2[0]-time<=0){
                        break;
                    }
                    int left = v2[0]-time;
                    time+=1;
                    score+=left;
                    i--;
                    v2.erase(v2.begin());
                    continue;
                }
            }
            if(v[i]-2*time<=0){
                break;
            }
            int left = v[i]-2*time;
            if(left>=2){
                time+=2;
                score+=left-1;
            }else {
                time+=1;
                score+=1;
            }
        }
        for(auto a: v2){
            if(a-time>0){
                int left = a-time;
                time+=1;
                score+=left;
            }
        }
        if(!cc&&v.empty()&&v2.empty()){
            cout << n << endl;
        }
        if(!v.empty()){
            cout << n-score << endl;
        }
    }
    
}