#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,ll bjj)
{
	while (pos <= n)
	{
		c[pos]+=val;
		if(bjj==0)bj[pos]=0;
		else bj[pos]+=bjj;
		pos += pos & (-pos);
	}
}
ll cal(ll i)
{
	if(c[i]&&a[i]==0)return -c[i];
	return 0;
}
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)
		{
			add(i,1,1);
			ans++;
		}
		else {
			if(bj[i]<1)ans++;
			add(i,-c[i],0);
		}
		printf("%lld\n",ans);
	}
	return 0;
}