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

using namespace std;
typedef long long ll;
pair <int, int> T[500010];
int  a, n, x, p, y, w, z, s, l;
string k;

bool por(pair <ll, ll> z,pair <ll, ll> b){
    if (b.first==z.first){
        return z.second<b.second;
    }
    else{
        return b.first<z.first;
    }

}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> p;
    while (p>0){

        cin >> n >> k;
        a=0;
        y=0;
        w=0;
        x=0;
        while (k[a]!=0){

            if (k[a]=='1'){
                if (x>0&&w==1){
                    if (x==1){
                        T[y].first=1;
                        T[y].second=2;
                    }
                    else {
                        T[y].first=x-1;
                        T[y].second=2;
                    }
                    y++;

                }
                else if (x>0&&w==0){

                    T[y].first=x;
                    T[y].second=1;
                    y++;

                }
                x=0;
                w=1;
            }
            else {
                x++;
            }
            a++;

        }

        if (x>0){
            T[y].first=x;
            T[y].second=1;
            y++;
        }
        sort (T, T+y, por);
        a=0;
        s=0;
        l=0;
        while(y>0){
            //cout << T[a].first << " " << T[a].second << " "<< s <<endl;

            if(T[a].first-(T[a].second*a)>0){
                s=s+T[a].first-(T[a].second*l);
            }
            else if(T[a].first-(T[a].second*l)==0&&T[a].first>1){
                s++;
            }
            l=l+T[a].second;
            T[a].first=0;
            T[a].second=0;
            y--;
            a++;
        }
        cout << n-s << endl;
        //cout << "=================="<< endl;
        p--;
    }
}