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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
int n,k,t;
string s;
// length, borders, (last_update),  
set <pair<int,int>>  v1;
set <pair<int,int>>  v2;
void readData(){
    v1.clear();
    v2.clear();
    scanf("%d", &n);
    cin>>s;
    // cout<<s;
    int zeros = 0;
    bool first = true;
    for (int i =0; i < s.size(); i++){
        if (s[i] == '0'){
            zeros ++;
        }else{
            if (first){
                if ( zeros > 0)
                    v1.insert(make_pair((-1)*zeros,-i));
                zeros = 0;
                first = false;
           }else{
            if ( zeros > 0)
                v2.insert(make_pair((-1)*zeros, i));
            zeros = 0;
           }
       }
    }
    if ( zeros > 0 ){
            v1.insert(make_pair((-1)*zeros,(s.size()-1)*(-1) ));
    }
}
void print_v1 (){
    auto it = v1.begin();
    for (; it != v1.end(); ++it) {
        pair<int,int>  p = *it; // Note the "*" here
        cout<<p.first << "  "<< p.second <<"\n";
    }
}

void print_v2 (){
    auto it = v2.begin();
    for (; it != v2.end(); ++it) {
        pair<int,int>  p = *it; // Note the "*" here
        cout<<p.first << "  "<< p.second <<"\n";
    }
}


int getAns(){
    int time = 0;
    long long score = 0;
    for ( ; v1.begin()!=v1.end() || v2.begin()!=v2.end(); time++){
        // cout<<"TIME : "<<time<<"score : "<<score<<"\n"<<"v1:\n";
        // print_v1();
        // cout<<"v2:\n";
        // print_v2();
        if (v1.begin()==v1.end()){
            pair<int,int> p = *v2.begin();
            v2.erase(v2.begin());
            p.first+=time;
            if ( p.first < 0 ){
                v1.insert(p);
            }
            continue;
        }

        //v1 not empty
        pair<int,int> p1 = *v1.begin();
        if (v2.begin()!=v2.end()){
            pair<int,int> p2 = *v2.begin();

            if ( p2.first * (-1)  > p1.first * (-1) + 1){
                v2.erase(v2.begin());
                p2.first += time;
                if ( p2.first < 0 ){
                    v1.insert(p2);
                }
                continue;

            } else{
                v1.erase(v1.begin());
                p1.first+=time;
                if (p1.first < 0 ){
                    score += (-1) * p1.first;
                }
                else{
                    if (p1.second >= 0)
                        score++;
                }
                
            }

        } else{
            v1.erase(v1.begin());
            p1.first+=time;
            if (p1.first < 0 ){
                score += (-1) * p1.first;
            } else {
                if (p1.second >= 0)
                        score++;
            }
        }

    }

    return n-score;
    
}

int main(){
    scanf("%d", &t);
    for (int i = 0; i< t; i++){
        readData();
        int ans = getAns();
        printf("%d\n", ans );
    }



}