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

using namespace std;

int t;

int n;

string s;

vector<int> queue2;
vector<int> queue1;

void solve(){
    cin>>n;
    cin>>s;

    queue1.clear();
    queue2.clear();

    int p=0;

    while(s[p] == '0' && p < s.size())
        p++;

    int q = s.size() - 1;

    while(s[q] == '0' && q >= 0)
        q--;

    if(p == s.size()){
        cout<<0<<endl;
        return;
    }

    queue1.push_back(p);
    queue1.push_back(s.size() - 1 - q);

    for(int i=p; i<=q; i++){
        if(s[i] == '1')
            queue2.push_back(0);
        else
            queue2.back()++;
    }

    sort(queue1.begin(), queue1.end());
    sort(queue2.begin(), queue2.end());

    int time=0, saved=0;
    int top1,top2,top1_2;

    while(true){
        if(!queue2.empty())
            top2 = queue2.back() - 2 * time;
        else
            top2 = 0;
        
        if(!queue1.empty())
            top1 = queue1.back() - time;
        else
            top1 = 0;
        
        if(queue1.size() >= 2)
            top1_2 = queue1[queue1.size()-2] - time;
        else
            top1_2 = 0;
        

        if(top2 <= 0 && top1 <= 0)
            break;

        if(top1_2 > 0 && top1_2 == top1 && top1 + top1_2 > top2){
            saved += top1 + top1_2 - 1;
            time += 2;
            queue1.pop_back();
            queue1.pop_back();
        }
        else if(top2 > 0 && (top2 > top1 + 1 || top1 <= 0)){

            saved += top2 - 1 + (top2 == 1);
            time +=2;

            queue2.pop_back();
        } else if(top1 >= 0){
            saved += top1;
            time ++;
            queue1.pop_back();
        }
    }

    cout<<n - saved<<endl;

}

int main() {

    cin>>t;

    for(int i=0;i<t;i++)
        solve();

    return 0;
}