#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	char c=getchar();
	int f=1,x=0;
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
	return f*x;
}
const int N=1e6+6;
int T,n;
char s[N];
int pl[N],pr[N],el[N],er[N];
int main(){
	T=read();
	while(T--){
		int cnt=0,ans=0;
		n=read();
		scanf("%s",s+1);
		for(int i=1;i<=n;i++){
			if(s[i]=='1'){
				++cnt;
				pl[cnt]=pr[cnt]=1-i;
				er[cnt]=1;
				break;
			}
		}	
		int now=0;
		s[n+1]='0';
		for(int i=1;i<=n+1;i++){
			if(s[i]=='1') now++;
			else if(now>0){
				++cnt;
				pr[cnt]=i-1,pl[cnt]=i-1-now+1;
				if(now>1) el[cnt]=er[cnt]=1;
				else el[cnt]=er[cnt]=0;
				now=0;
			}
		}
		for(int i=n;i>=1;i--){
			if(s[i]=='1'){
				++cnt;
				pl[cnt]=pr[cnt]=n+1+n-i;
				el[cnt]=1;
				break;
			}
		}
		for(int i=2;i<cnt;i++){
			if(pl[i]==pr[i]){
				int dl=pl[i]-pr[i-1],dr=pl[i+1]-pr[i];
				if(dl>dr) el[i]=1;
				else if(dr>dl) er[i]=1;
				else{
					if(er[i-1]) er[i]=1;
					else el[i]=1;
				}
			}
		}
		//
//		for(int i=1;i<=cnt;i++){
//			printf("%d:pl,pr: %d %d\n",i,pl[i],pr[i]);	
//			printf("%d:el,er: %d %d\n",i,el[i],er[i]);
//		}
//		//
		for(int i=1;i<cnt;i++){//calc i to i+1 time
			int d=pl[i+1]-pr[i]-1,t=1;
			if(!d) t=0;
			else{
				if(er[i]) d--;
				if(el[i+1]) d--;
				if(d>0) t+=(d-1)/2+1;
			}
//			printf("t[%d]:%d\n",i,t);
			ans=max(ans,t);
		}
		printf("%d\n",ans);
	}
	
	return 0;
}