#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define db double
const int mod=1e9+7;
const int N=2e5+5;


void abt() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=' '+s;
    int jud=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='0') jud=1;
    }
    if(!jud){
        cout<<0<<'\n';
        return ;
    }
    vector<int> idx(n+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='1'){
            if(i-1>=1&&i+1<=n){
                if(s[i-1]=='1'){
                    idx[i+1]=1;
                }
                if(s[i+1]=='1'){
                    idx[i-1]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(idx[i]) s[i]='1';
    }
    vector<pair<int,int>>a;
    int cnt=1;
    for(int i=2;i<=n;i++){
        if(s[i]!=s[i-1]){
            int t=0;
            if(s[i]=='0') t=1;
            a.push_back({cnt,t});
            cnt=1;
        }else{
            cnt++;
        }
    }
    if(s[n]=='1'){
        a.push_back({cnt,1});
    }else{
        a.push_back({cnt,0});
    }
    int siz=a.size();
    for(int i=0;i<siz;i++){
        auto [t1,t2]=a[i];
        if(t2==1&&t1>1) continue;
        if(t2==1&&t1==1){
            if(i==0){
                a[i+1].first--;
            }else if(i==siz-1){
                a[i-1].first--;
            }else{
                if(a[i-1].first>=a[i+1].first){
                    a[i-1].first--;
                }else{
                    a[i+1].first--;
                }
            }
        } 
    }
    int ans=0;
    for(int i=0;i<siz;i++){
        if(a[i].second==0){
            if(i==0||i==siz-1){
                ans=max(ans,a[i].first);
            }else{
                ans=max(ans,(a[i].first+1)/2);
            }
        }
    }
    cout<<ans+1<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout<<fixed<<setprecision(9);
    int T=1;
    cin>>T;
    while(T--) abt();
    return 0;
}