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

using namespace std;

string s;
vector < pair < int , int > > V;
int main(void){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        cin >> s;
        int akt = 0;
        for(int i = 0; i < n;i++){
            if(s[i] == '1'){
                if(akt){
                    if(akt == i){
                        V.push_back({akt,1});
                    }else{
                        V.push_back({akt,2});
                    }
                }
                akt = 0;
            }else{
                akt++;
            }
        }
        if(akt)
            V.push_back({akt,1});

        int ans = 0;
        while(!V.empty()){
            int ma = 0;
            int id = 0;
            for(int i = 0; i < V.size();i++){
                if(V[i].first * (2 / V[i].second) > ma){
                    ma = V[i].first * (2 / V[i].second);
                    id = i;
                }
            }
            ans++;
            V[id].second--;
            V[id].first--;
            if(V[id].second == 0){
                ans += V[id].first;;
                swap(V[id],V.back());
                V.pop_back();
            }
            for(int i = V.size()-1; i >= 0;i--){
                V[i].first -= V[i].second;
                if(V[i].first <= 0){
                    swap(V[i],V.back());
                    V.pop_back();
                }
                if(V[i].first == 1){
                    V[i].second = 1;
                }
            }
        }
        printf("%d\n",n-ans);
        V.clear();
    }

    return 0;
}