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

int t;
long long n;
string s;
long long i, ile, l, r;
priority_queue<long long> pq;
long long czas, cur, res;

void solve()
{
    cin >> n;
    cin >> s;
    ile = 0, l = 0, r = 0;
    pq = priority_queue<long long>();
    czas = 0, cur = 0, res = 0;

    for (i = 0; i < n; ++i)
        if (s[i] == '0')
            ile++;
        else
            break;
    if (ile == n)
    {
        cout << "0\n";
        return;
    }
    l = ile;
    ile = 0;
    for (i; i < n; ++i)
    {
        if (s[i] == '0')
            ile++;
        else
        {
            if (ile > 0)
                pq.push(ile);
            ile = 0;
        }
    }
    r = ile;

    while (!pq.empty() || l > czas || r > czas) // brak środkowych i skrajnych
    {
        cur = 0;
        if (!pq.empty()) // dalej trzeba rozpatrzyć skrajne
            cur = pq.top();
        if (cur <= 2 * czas && l <= czas && r <= czas) // wszystkie już chore
            break;
        if (cur - 2 * czas <= l - czas + 2 && l > czas && l >= r) // lepiej skrajne niż środkowe (lewy jest lepszy niż prawy)
        {
            res += l - czas;
            l = 0;
            czas += 1;
        }
        else if (cur - 2 * czas <= r - czas + 2 && r > czas) // lepiej skrajne niż środkowe (prawy jest gorszy niż lewy)
        {
            res += r - czas;
            r = 0;
            czas += 1;
        }
        else if (cur - 2 * czas == 1) // zaszczepimy tylko 1 miasto ze środkowego
        {
            res++;
            czas++;
            pq.pop();
        }
        else // oddzielimy przedział miast dłuższy od 1
        {
            res += cur - 2 * czas - 1;
            czas += 2;
            pq.pop();
        }
    }
    cout << n - res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> t;
    while (t--)
        solve();
}