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

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    priority_queue < int> q_1, q_2;
    int n, t;
    string line;

    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cin >> t;
        cin >> line;

        int licz = 0, ile;
        int wynik = 0;
        for (int z = 0; z < t; z++) {
            if (line[z] == '0') {
                licz++;
            }
            else {
                if(licz) {
                    if (licz != z)
                        q_2.push(licz);
                    else
                        q_1.push(licz);
                }
                licz = 0;
                wynik++;
            }
        }
        if (licz > 0)
            q_1.push(licz);

        ile = 0;

        while (!q_1.empty() || !q_2.empty()) {
            int b = INT32_MIN, a = b, pow = 1;
            if (!q_1.empty())
                a = q_1.top();
            if (!q_2.empty())
                b = q_2.top();

            if (a == INT32_MIN || b == INT32_MIN) {
                if (a == INT32_MIN){
                    a = b;
                    pow = 2;
                    q_2.pop();
                }
                else   
                    q_1.pop();
            }
            else {
                if ((a - ile) * 2 >= b -2 * ile) { // a is bigger
                    q_1.pop();
                }
                else { 
                    a = b;
                    pow = 2;
                    q_2.pop();
                }
            }


            if (a - ile * pow > 0) {
                wynik += ile;
                if (pow == 2)
                    q_1.push(a - ile - 1);
                
                ile ++;
            }
            else {
                wynik += a;
            }
        }
        cout << wynik << "\n";
    }
}