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
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#include <random>
#define ll long long int
#define pb push_back
#define st first
#define nd second
#define pii pair<int,int>
#define mp make_pair
#define pll pair<long long,long long>
#define ld long double
#define ull unsigned long long

using namespace std;

const int nax = 1e6 + 5;
int n;
int a[nax];

bool cmp(pii one, pii two){
    if(one.nd == two.nd) return one.st < two.st;
    int s1 = one.st * two.nd;
    int s2 = one.nd * two.st;
    if(s1 != s2) return s1 < s2;
    return one.nd < two.nd;
}

void solve(){
    cin >> n;
    string s; cin >> s;
    for(int i=1;i<=n;i++){
        a[i] = s[i - 1] - '0';
    }

    vector<pii> values;
    int pr = 0;
    while(pr < n && a[pr + 1] == 0) pr += 1;
    if(pr == n){
        cout << 0 << "\n";
        return;
    }
    int sf = n + 1;
    while(sf > 1 && a[sf - 1] == 0) sf -= 1;
    sf = n - sf + 1;
    if(pr) values.pb(mp(pr, 1));
    if(sf) values.pb(mp(sf, 1));
    int id1 = 1;
    int id2 = n;
    while(a[id1] == 0) id1 += 1;
    while(a[id2] == 0) id2 -= 1;
    int cur = 0;
    for(int i=id1;i<=id2;i++){
        if(a[i] == 1){
            if(cur){
                values.pb(mp(cur, 2));
            }
            cur = 0;
        }
        else cur += 1;
    }
    if(cur){
        values.pb(mp(cur, 2));
    }
    sort(values.begin(), values.end(), cmp);
    reverse(values.begin(), values.end());

    int saved = 0;
    int turn = 0;
    for(pii cur : values){
        if(cur.nd == 1){
            int lft = cur.st - turn;
            if(lft <= 0) continue;
            saved += lft;
            turn += 1;
        }
        else{
            int lft = max(0, cur.st - turn * 2);
            if(lft == 0) continue;
            saved += 1;
            lft -= 2;
            turn += 1;
            if(lft > 0){
                turn += 1;
                saved += lft;
            }
            else continue;
        }
    }
    cout << n - saved << "\n";
}

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

    int tt = 1;
    cin >> tt;
    while(tt--) solve();

    return 0;
}