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

#define  _2137 0

#define pb push_back
#define ff first
#define ss second

using namespace std;

bool visited[500007];

int main() {

	int n,m;
    scanf("%d",&n);
    vector <int> ans;
    vector <pair <int,bool> > tab;

    char g;
    bool check;
    for(int i=0,temp;i<n;++i){

        scanf("%d",&m);
        scanf(" %c",&g);
        temp=0;
        if(g=='0'){
            ++temp;
            check=true;
        }
        else check=false;
        int mx=0,loc;
        
        for(int i=2;i<m;++i){
            scanf(" %c",&g);
            if(g=='1'){
                if(temp!=0){
                    tab.pb({temp,false});
                    if(temp>mx){
                        mx=temp;
                        loc=tab.size()-1;
                    }
                    temp=0;
                }
            }
            else ++temp;

        }
        scanf(" %c",&g);

        if(g=='0'){
            ++temp;
        }

        if(check && temp>0 && tab.size()==0) {
            ans.pb(0);
            continue;
        }

        if(temp>0) tab.pb({temp,true});

        if(check) tab[0].ss=true;
        int out=0,change=0;

        if(tab[loc].ss){
            out+=mx;
            tab.erase(tab.begin()+loc);
            ++change;
        }
        else{
            int siz=tab.size()-1;
            if(tab[0].ss && tab[siz].ss && tab[0].ff + tab[siz].ff >= mx ){

                out+=tab[0].ff+tab[siz].ff-1;
                change+=2;
                tab.erase(tab.end());
                tab.erase(tab.begin());
                
            }
            else{
                out+=mx-1;
                change+=2;
                tab.erase(tab.begin()+loc);
            }

        }
        //cout<<mx<<" "<<loc<<" "<<out<<" "<<change<<endl;
        sort(tab.begin(),tab.end(),greater<pair<int,bool>>());

        for(int i=0;i<tab.size();++i){
            if(tab[i].ss){
                if(tab[i].ff-change>0){
                    out+=tab[i].ff-change;
                    ++change;
                }
                else break;
            }
            else{
                if(tab[i].ff-(change*2)>0){
                    out+=max(tab[i].ff-(change*2)-1,1);
                    change+=2;
                }
                else break;
            }
        }
        ans.pb(m-out);

        tab.clear();

    }

    for(auto i:ans){
        printf("%d\n",i);
    }
	
	return _2137;
}