#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e6+10,INF=1e9;
int T,n;
char a[N];
int f[N][2];
void get(){
	scanf("%d%s",&n,a+1);
	vector<int>p;
	for(int i=1;i<=n;i++)if(a[i]=='1')p.push_back(i);
	int len=p.size();
	for(int i=0;i<len;i++){
		for(int j=0;j<2;j++)f[i][j]=INF;
	}
	f[0][0]=p[0]-1,f[0][1]=p[0]>1?p[0]:0;
	for(int i=1;i<len;i++){
		int cnt=p[i]-p[i-1]-1;
		if(!cnt){
			f[i][0]=f[i][1]=min(f[i-1][0],f[i-1][1]);
		}else{
			f[i][0]=min(max(f[i-1][0],cnt/2+1),max(f[i-1][1],(cnt+1)/2));
			f[i][1]=min(max(f[i-1][0],(cnt+1)/2+1),max(f[i-1][1],cnt/2+1));
		}
	}
	// debug(f[len-1][0],f[len-1][1]);
	int res1=p.back()<n?max(f[len-1][0],n-p.back()+1):f[len-1][0];
	int res2=max(f[len-1][1],n-p.back());
	printf("%d\n",min(res1,res2));
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}