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

const int INF=999999999;
int main()
{   
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    while(n--)
    {
        int t;
        string ciag="";
        cin>>t;
        cin>>ciag;
        vector<int> c2V,c1V;
        queue<int> c2;
        queue<int> c1;
        int dl=0;
        for(int i=0 ; i<t ; i++) {
            if(ciag[i]=='0') {
            dl++;
            }
            else if(dl>0) {
            if(c1V.empty() && ciag[0]=='0') c1V.push_back(dl);
            else c2V.push_back(dl);
            dl =0;
            }
            //cout<<"I "<<i<<" dl "<<dl<<endl;
        }
        c1V.push_back(dl);
        sort(c2V.begin(),c2V.end(),greater<int>());
        sort(c1V.begin(),c1V.end(),greater<int>());
        for(auto i : c2V) { c2.push(i);}
        for(auto i : c1V) {c1.push(i);}
        c2.push(-INF);
        c1.push(-INF);
        c2V.clear();
        c1V.clear();
        int uratowano =0;
        int dni_uplynelo =0;
        while(true) {
          //cout<<"C2 front"<<c2.front()<<endl;
          //cout<<"C1 front"<<c1.front()<<endl;
            if(c1.front()-dni_uplynelo>=c2.front()-dni_uplynelo*2-2 && c1.front()>dni_uplynelo) {
                uratowano+=c1.front()-dni_uplynelo;
                dni_uplynelo++;
                c1.pop();
            }
            else if(c2.front()>dni_uplynelo*2){
                if(c2.front()-dni_uplynelo*2>2) {
                uratowano+=c2.front()-dni_uplynelo*2-1;
                dni_uplynelo+=2;
                }
                else {
                    uratowano+=1;
                    dni_uplynelo+=1;
                }
                c2.pop(); 
            }
            else break;
        }
        //cout<<uratowano<<endl;
        //cout<<dni_uplynelo<<endl;
        cout<<t-uratowano<<endl;
        
    }


    return 0;
}