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
/******************************************************************************

                            Online C Compiler.
                Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 100009



int main()
{
    int t;
    std::cin >> t;
    std::string initialState;
    
    while (t--) {
        int n, leftmostInterval = 0, rightmostInterval = 0;
        std::vector<std::pair<int, int>> intervals;
        std::cin >> n >> initialState;
        
        bool isFirst = true;
        int currentInterval = 0;
        for (char &c : initialState) {
            if (c == '0') {
                rightmostInterval = currentInterval += 1;
                if (isFirst) leftmostInterval = currentInterval;
            } else {
                if (!isFirst && currentInterval) intervals.push_back(std::make_pair(-currentInterval, 2));
                isFirst = false;
                currentInterval = rightmostInterval = 0;
            }
        }
        
        if (leftmostInterval) intervals.push_back(std::make_pair(-leftmostInterval * 2, 1));
        if (rightmostInterval) intervals.push_back(std::make_pair(-rightmostInterval * 2, 1));
        
        std::sort(intervals.begin(), intervals.end());
        
        // for (int i=0; i<intervals.size(); i++) std::cout << -intervals[i].first << " ";
        // std::cout << "\n";
        
        int savedCities = 0, roundNumber = 0;
        for (int i=0; i<intervals.size(); i++) {
            int fst = -intervals[i].first, cnt = intervals[i].second;
            int intervalCurrent = std::max(0, fst - 2 * roundNumber);
            // std::cout << fst << " " << intervalCurrent << " <- int current \n";
            if (cnt == 1) {
                savedCities += intervalCurrent / 2;
            } else {
                if (intervalCurrent > 1) intervalCurrent -= 1;
                savedCities += std::max(0, intervalCurrent);
            }
            roundNumber += cnt;
        }
        
        if (isFirst) savedCities = n;
        std::cout << std::max(0, n - savedCities) << "\n";
    }
}