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
#include<cstdio>
#include<vector>
#include<algorithm>

char input[1000*1000];

void cass(int n) {
    std::vector<std::pair<int, int> > v;
    int first_occ = n;
    for(int i = 0; i < n; ++i) {
        if (input[i] == '1') {
            first_occ = i;
            break;
        }
    }
    
    if (first_occ == n) {
        printf("0\n");
        return;
    }
    
    if (first_occ != 0)
        v.push_back(std::make_pair(first_occ, 1));
    int counter = 0;
    for (int i = first_occ; i < n; ++i) {
        if (input[i] == '0')
            counter++;
        else if (counter > 0 and input[i] == '1') {
            v.push_back(std::make_pair(counter, 2));
            counter = 0;
        } else if (counter > 0 and i == (n-1)) {
            v.push_back(std::make_pair(counter, 1));
        }
    }
    
    for (int i = 0; i < v.size(); ++i)
        v[i].first = -v[i].first;
    
    std::sort(v.begin(), v.end());
    
    for (int i = 0; i < v.size(); ++i)
        v[i].first = -v[i].first;
    
    int time = 0;
    int res = 0;
    for (int i = 0; i < v.size(); ++i) {
        if (time < v[i].first) {
            ++time;
            v[i].second--;
        }
        if (time < v[i].first and v[i].second > 0) {
            ++time;
        }
        if (time < v[i].first)
            res += v[i].first - time;
    }
    
    printf("%i\n", n-res);
    
    //for(int i = 0; i < v.size(); ++i)
    //    printf("%i %i", v[i].first, v[i].second);
    //printf("\n");
}

int main() { 
    int t;
    scanf("%i", &t);
    while(t--) {
        int n;
        scanf("%i", &n);
        scanf("%s", input);
        cass(n);        
    }
    
    return 0;
}