#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, bool>

struct Cmp {
    bool operator()(pii a, pii b) {
        return a.first+(a.second ? a.first : 0) < b.first+(b.second ? b.first : 0);
    }
};

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

    int t;
    cin>>t;

    while (t--) {
        int n;
        cin>>n;

        string s;
        cin>>s;

        bool hasV = false;
        for (int i=0; i<n; ++i) {
            if (s[i] == '1') {
                hasV = true;
                break;
            }
        }

        if (!hasV) {
            cout<<0<<endl;
            continue;
        }

        priority_queue<pii, vector<pii>, Cmp> pq;

        int tmp = 0;
        bool left=true;
        for (int i=0; i<n; ++i) {
            if (s[i] == '0') ++tmp;
            else {
                if (tmp > 0) pq.push({tmp, left});
                left = false;
                tmp = 0;
            }
        }
        if (tmp > 0) pq.push({tmp, true});

        //cout<<pq.top().second<<endl;
        int c = 0, safe=0;
        while (!pq.empty()) {
            pii v = pq.top();
            pq.pop();

            //cout<<"got "<<v.first<<endl;

            if (v.second) {
                safe += max(0, v.first-c);
                ++c;
            } else {

                if (v.first-2*c == 1) safe += 1;
                else safe += max(0, v.first-2*c-1);
                c += 2;
            }
        }

        cout<<n-safe<<endl;
    }
}