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
//przyspieszyc
#include <bits/stdc++.h>
#define f first
#define s second
#define add push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pint;
const int N = 1e5+5;
char T[N];
vector< pair< pint , bool > > W;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t,n,len,mx,odp;
    pair< pint , bool > pom;
    pair< pint , bool > *pom2;
    vector<int> jedynki;

    cin >> t;
    while(t--)
    {
        odp = 0;
        jedynki.clear();
        cin >> n;

        for(int i=0; i<n; i++)
        {
            cin >> T[i];
            if(T[i]=='1') jedynki.add(i);
        }

        if(jedynki.empty())
        {
            cout << 0 << '\n';
            continue;
        }

        for(int i=0; i<jedynki.size()-1; i++)
        {
            if(jedynki[i]+1 != jedynki[i+1]) W.add({{jedynki[i]+1, jedynki[i+1]-jedynki[i]-1},1});
        }
        if(jedynki.back()!=n-1) W.add({{jedynki.back()+1, 2*(n-jedynki.back()-1)},0});
        if(jedynki[0]!=0) W.add({{0, 2*jedynki[0]},0});

        //for(auto i : W) cout << i.f.f << ' ' << i.f.s << '\n';

        while(true)
        {
            mx=0;
            for(pair< pint , bool > &i : W)
            {
                if(i.f.s>mx)
                {
                    mx=i.f.s;
                    pom=i;
                    pom2=&i;
                }
            }

            //cout << mx << ' ' << odp << '\n';

            if(mx==0){
                cout << n-odp << '\n';
                break;
            }

            if(pom.s) //100...001
            {
                odp+=pom.f.s-1;
                for(pair< pint , bool > &i : W)
                {
                    i.f.s-=4;
                    if(i.s && (i.f.s==1 || i.f.s==2))
                    {
                        i.f.s=2; i.s=0;
                    }
                }
            }
            else //100...00 OR 101
            {
                odp+=pom.f.s/2;
                for(pair< pint , bool > &i : W)
                {
                    i.f.s-=2;
                    if(i.s && (i.f.s==1 || i.f.s==2))
                    {
                        i.f.s=2; i.s=0;
                    }
                }
            }

            (*pom2).f.s=0;
        }
    }

	return 0;
}