#include<bits/stdc++.h>
#define ll long long
#define inf 1e18
#define mn 1000005
using namespace std;
ll a[mn],c[mn],bj[mn],ans,n,m;
string s;
inline ll low(ll x)
{
	return (x & (-x));
}
void add(ll pos,ll val,bool bjj)
{
	while (pos <= n)
	{
		c[pos]=val;
		if(bjj==0)
		{
			bj[pos]=0;
		}
		else bj[pos]+=1;
		pos += pos & (-pos);
	}
}
int main()
{
	ll t,x,y,z,i,j,k;
	cin>>t;
	while(t--)
	{
		scanf("%lld",&n);
		cin>>s;
		for(i=1;i<=n;i++)
		{	
			a[i]=s[i-1]-'0';
			c[i]=bj[i]=0;
		}
		ans=0;
		for(i=1;i<=n;i++)
		if((c[i]&&a[i])||(c[i]==0&&a[i]==0))continue;
		else if(a[i]&&(c[i]==0))
		{
      ans++;
			add(i,a[i],1);
		}
		else {
			if(bj[i]<2)ans++;
			add(i,a[i],0);
		}
		printf("%lld\n",ans);
	}
	return 0;
}