#include <bits/stdc++.h>

using namespace std;

bool cmp (int i,int j) { return (i>j); }

int main() {
    //cout <<"xD";
    int N;
    cin >> N;
    char c;
    for (int i = 0; i < N; i++){
        int n;
        vector<int> v = {0};
        cin >> n;
        bool prev = true;
        for (int j = 0; j < n; j++){
            cin >> c;
            if (c == '0') {
                if (prev) v.back()++;
                else v.push_back(1);
                prev = true;
            }
            else prev = false;
        }
        if (c == '1') v.push_back(0);
        if (v.size() == 1) {cout << "0\n"; continue;}
        int left = v.front(), right = v.back();
        sort(v.begin() + 1, v.end() - 1, cmp);
        int index = 1, turn = 0, score = 0;
        while ((index < v.size() - 1 && v[index] - 2*turn > 0) || left - turn > 0 || right - turn > 0 ){
            if (v[index] - 2*turn > left - turn && v[index] - 2*turn > right - turn){
                if (v[index] - 2*turn > 1) score += v[index] - 2*turn - 1;
                else score += 1;
                //cout <<"SCORE(center): " << score << endl;
                turn++;
                index++;
            }
            else if (left > right){
                score += left - turn;
                //cout <<"SCORE(left): " << score << endl;
                left = -1;
            }
            else{
                score += right - turn;
                //cout <<"SCORE(right): " << score << endl;
                right = -1;
            }
            turn++;
        }
        cout << n - score << endl;
    }
    return 0;
}