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

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

const int N=2e5+5;
int n;
char c[N];

inline bool check()
{
	for(int i=1;i<=n;i++)
	{
		if(c[i]=='1') continue;
		int now=i;
		while(now<=n && c[now]=='0') now++;
		if(now-i>1) return false;
		i=now-1;
	}
	return true;
}

int main()
{
	int T=read();
	while(T--)
	{
		n=read();
		scanf("%s",c+1);
		int ans=0;
		for(int i=1;i<=n;i++)
			if(c[i]=='1') 
				ans++;
		if(c[1]=='1' && c[n]=='1' && check()) 
			ans++;
		printf("%d\n",ans);
	}
	return 0;
}