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

bool porownaj(int a, int b)
{
	return a>b;
}
long long n, k, wyn, t, start, koniec, m;
char a;
vector <int> drogi;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> m;
    for(long long i=0; i<m; i++)
    {
    drogi.clear();
    k=0;
    t=0;
    wyn=0;
    cin >> n;
    for(long long i=0; i<n; i++)
    {
         cin>>a;
         if(a=='1')
         {
             if(t>0)
             {//cout<<k<<" ";
                 drogi.push_back(k);
                 k=0;
             }
             else
             {//cout<<k<<" ";
                 start=k;
                 k=0;
                 t++;
             }
         }
         else
         {
             k++;
         }
    }
    //cout<<endl;
    koniec=k;
    if(t>0)
    {
        sort(drogi.begin(), drogi.end(), porownaj);
        k=0;
        while(drogi[k]-k*4-2>=0)
        {
            //cout<<drogi[k]<<endl;
            wyn=wyn+1+drogi[k]-k*4-2;
            k++;
            //cout<<wyn<<"a ";
        }
        k=k*2;
        if(start-k>0)
        {
            wyn=wyn+start-k;
            //cout<<wyn<<"b ";
            k++;
        }
        if(koniec-k>0)
        {
            wyn=wyn+koniec-k;
            //cout<<wyn<<"c ";
        }
        cout<<n-wyn<<endl;
    }
    else
    {
        cout<<"0"<<endl;
    }
    }
}