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
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<algorithm>

using namespace std;

int t, n;
char d;

multiset<int> singleset, doubleset;

void print(multiset<int> dupas)
{
    for (int const& dupa : dupas)
    {
        std::cout << dupa << ' ';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    for(int i = 0; i < t; i++) {
    	cin >> n;
    	singleset.clear();
    	doubleset.clear();
    	int ones = 0;
    	int zeros = 0;
    	bool was_one = false;
    	for(int j = 0; j < n; j++) {
    		cin >> d;
    		if (d == '0') {
    			zeros++;
    		} else if (d == '1') {
    			if (zeros > 0) {
    				if (was_one) {
    					doubleset.insert(zeros);
    				} else {
    					singleset.insert(zeros);
    				}
    				zeros = 0;
    			}
    			was_one = true;
    			ones++;
    		}
    	}
    	if (zeros > 0 && was_one) {
    		singleset.insert(zeros);
    	}


    	int iter = 1;
    	while (singleset.size() + doubleset.size()) {
            // cout << "----------------" << endl;
            // cout << "single" << endl;
            // print(singleset);
            // cout << endl << "double" << endl;
            // print(doubleset);
            // cout << endl;

    		if (singleset.size() > 0 && (doubleset.size() == 0 || 2 * (*(singleset.rbegin())) >= (*(doubleset.rbegin())))) {
                // cout << "bierzemy single " << (*(singleset.rbegin())) << endl;
    			singleset.erase(--singleset.end());
    		} else {
    			int tmp = *(doubleset.rbegin());
                // cout << "bierzemy double " << tmp << endl;
    			doubleset.erase(--doubleset.end());
                if (tmp - 2 * iter + 1 > 0) {
        			singleset.insert(tmp-iter); 
                }
    		}
    		ones += singleset.size();
    		ones += doubleset.size();
    		doubleset.erase(2 * iter - 1);
    		ones += doubleset.size();
    		doubleset.erase(2 * iter);
    		singleset.erase(iter);
    		iter++;
    	}
	    cout << ones << endl;
    }

}