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
#include <bits/stdc++.h>
using namespace std;
#define nd second
#define st first
#define pii pair<int,int>
#define pb push_back
typedef long long ll;

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

    int st1=-1, last1=-1;
    for(int i=0; i<n; i++)
        if(s[i]=='1'){
            st1=i;
            break;
        }

    for(int i=n-1; i>=0; i--)
        if(s[i]=='1'){
            last1=i;
            break;
        }
    
    if(st1==-1){
        cout<<"0";
        return;
    }

    vector<int>len;
    int cur0=0, sumins=0;
    for(int i=st1+1; i<=last1; i++){
        if(s[i]=='0') cur0++;
        else{
            len.pb(cur0);
            sumins+=cur0;
            cur0=0;
        }
    }
    sort(len.begin(), len.end());
    
    int led=(st1==-1? 0:st1), red=(last1==-1? 0:n-last1-1);
    int cnt=0, moves=0;
    
    while(!len.empty()){
        //cout<<len.back()<<" "<<moves<<'\n';
        int mid=len.back()-2*moves; //aktualna dlugosc
        int l=max(led-moves,0), r=max(red-moves, 0);

        if(mid<=0) break;
        if(mid<=2){ //mam jeden ruch: mid, prawy lub lewy
            int chosl=-1e9, chosr=-1e9, chosmid=-1e9;
            if(l>0) chosl=l-mid-(r>0);
            if(r>0) chosr=r-mid-(l>0);
            chosmid=1-(l>0)-(r>0);
            int maxval=max({chosl, chosr, chosmid});
            if(chosl==maxval){
                cnt+=l;
                moves++;
                led=0;
            }
            else if(chosr==maxval){
                cnt+=r;
                moves++;
                red=0;
            }
            else if(chosmid==maxval){
                cnt++;
                moves++;
                len.pop_back();
            }
        }
        else{ //moge albo zrobic mid albo (prawy i lewy)
            if(l==0 || r==0){
                cnt+=(mid-1);
                moves+=2;
                len.pop_back();
            }
            else{
                int chosmid=mid-3;
                int chosboth=l+r-3;
                if(chosmid>chosboth){
                    cnt+=(mid-1);
                    moves+=2;
                    len.pop_back();
                }
                else{
                    cnt+=(l+r-1);
                    led=0, red=0;
                    moves+=2;
                }
            }
        }
    }

    led-=moves;
    if(led>0){
        cnt+=led;
        moves++;
    }
    
    red-=moves;
    if(red>0){
        cnt+=red;
        moves++;
    }

    cout<<n-cnt<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(); cout.tie();

    int t;
    cin>>t;
    while(t--) solve();
}