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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
long long n, licz,t,jed,a,x,sz;
string s;
vector <long long> V;
vector <long long> X;
int main()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    for(int j=0; j<t; j++)
    {
        cin>>n;
        cin>>s;
        licz=0;
        jed=0;
        a=0;
        while(a<s.size())
        {
            if(s[a]=='0')
            {
                a++;
                licz++;
                while(s[a]=='0'&&a<s.size())
                {
                    licz++;
                    a++;
                }
            }
            if(a>=s.size()-1)
            {
                if(a==s.size()-1)
                {
                    V.push_back(licz);
                    licz=0;
                }
                if(a>s.size()-1)
                {
                    X.push_back(licz);
                    licz=0;
                }
                break;
            }
            if(s[a]=='1')
            {
                if(jed==0)
                {
                    if(licz>0)
                    {
                        X.push_back(licz);
                    }
                    jed=1;
                    licz=0;
                }
                else
                {
                    V.push_back(licz);
                    licz=0;
                }
                a++;
            }
        }
        if(jed == 0)
        {
            cout<<0<<endl;
        }
        else
        {
            sort(V.begin(), V.end());
            sort(X.begin(), X.end());
            x=0;
            sz=0;
            while(!V.empty()||!X.empty())
            {
                if(V.empty())
                {
                    if(X[X.size()-1]-x>0)
                    {
                        sz+=X[X.size()-1]-x;
                        X.pop_back();
                    }
                    else
                    {
                        break;
                    }
                }
                else if(X.empty())
                {
                    if(V[V.size()-1]-(x*2)>2)
                    {
                        sz+=(V[V.size()-1]-(x*2)-1);
                        V.pop_back();
                        x++;
                    }
                    else if(V[V.size()-1]-(x*2)==2)
                    {
                        sz+=(V[V.size()-1]-(x*2)-1);
                        V.pop_back();
                    }
                    else if(V[V.size()-1]-(x*2)==1)
                    {
                        sz+=V[V.size()-1]-(x*2);
                        V.pop_back();
                    }
                    else
                    {
                        break;
                    }
                }
                else if((V[V.size()-1]-(x*2)-1)<=0 && (X[X.size()-1]-x)<=0)
                {
                    break;
                }
                else if(!X.empty()&&!V.empty()&&((V[V.size()-1]-(x*2))>(X[X.size()-1]-x+1)))
                {
                   if(V[V.size()-1]-(x*2)>2)
                    {
                        sz+=(V[V.size()-1]-(x*2)-1);
                        V.pop_back();
                        x++;
                    }
                    else if(V[V.size()-1]-(x*2)==2)
                    {
                        sz+=(V[V.size()-1]-(x*2)-1);
                        V.pop_back();
                    }
                    else if(V[V.size()-1]-(x*2)==1)
                    {
                        sz+=V[V.size()-1]-(x*2);
                        V.pop_back();
                    }
                    else
                    {
                        continue;
                    }
                }
                else if(!X.empty()&&!V.empty()&&((V[V.size()-1]-(x*2))<=(X[X.size()-1]-x+1)))
                {
                    if(X[X.size()-1]-x>0)
                    {
                        sz+=X[X.size()-1]-x;
                        X.pop_back();
                    }
                    else
                    {
                        continue;
                    }
                }
                x++;
            }
            V.clear();
            X.clear();
            cout<<n-sz<<endl;
        }
    }
    return 0;
}