#include <bits/stdc++.h>
using namespace std;

const int N=100050;
char s[N];
int p[N];
int Find(int x){return p[x]==x?x:p[x]=Find(p[x]);}
void Union(int x,int y){
	x=Find(x);
	y=Find(y);
	if(x==y)return;
	p[x]=y;
}
int main(){
	int t;
	scanf("%i",&t);
	while(t--){
		int n;
		scanf("%i",&n);
		scanf("%s",s+1);
		for(int i=0;i<=n;i++)p[i]=i;
		for(int i=1;i<=n;i++){
			if(s[i]=='0'){
				Union(i,i-(i&-i));
			}
		}
		set<pair<int,int>> bad;
		for(int i=1;i<=n;i++){
			if(s[i]=='1'){
				bad.insert({Find(i),Find(i-(i&-i))});
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			if(Find(i-1)!=Find(i)){
				int x=Find(i-1);
				int y=Find(i);
				if(bad.count({x,y}) || bad.count({y,x}))
					ans++;
			}
		}
		printf("%i\n",ans);
	}
	return 0;
}