#include<bits/stdc++.h>
#define ll long long
#define inf 1e18
#define mn 1000005
using namespace std;
ll a[mn],c[mn],ans,n,m;
string s;
inline ll low(ll x)
{
	return (x & (-x));
}
void add(ll pos,ll val)
{
	while (pos <= n)
	{
		c[pos]+=val;
		pos += pos & (-pos);
	}
}
ll cal(ll i)
{
	while (i <= n)
	{
		if(c[i]&&a[i]==0)return -c[i];
		i+=low(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]=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)
		{
			x=cal(i);
			if(x==0)x=1;
			add(i,x);
			ans++;
		}
		else {add(i,-c[i]);ans++;}
		printf("%lld\n",ans);
	}
	return 0;
}