/*
https://kaiserwilheim.github.io/solutions/solution-cf103861l/
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define For(i,l,r) for(int i=(l);i<=(r);i++)
#define Rof(i,l,r) for(int i=(l);i>=(r);i--)
constexpr int N=100005;
int T,n,f[N][2],g[2];
char s[N];
vector<int>e[N],rt;
void dfs(int u){
	f[u][0]=0,f[u][1]=1;
	for(int v:e[u]){
		dfs(v);
		g[0]=inf,g[1]=inf;
		g[0]=min(f[u][0]+f[v][0],f[u][1]+f[v][1]);
		g[1]=min({f[u][0]+f[v][1],f[u][1]+f[v][0],f[u][1]+f[v][1]});
		f[u][0]=g[0],f[u][1]=g[1];
	}
	if(s[u]=='0') f[u][1]=inf;
	else f[u][0]=inf;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		cin>>(s+1);
		rt.clear();
		For(i,1,n) e[i].clear();
		For(i,1,n){
			int fa=i+(i&(-i));
			if(fa<=n) e[fa].push_back(i);
			else rt.push_back(i);
		}
		int ans=0;
		for(int u:rt) dfs(u),ans+=min(f[u][0],f[u][1]);
		cout<<ans<<'\n';
	}
	return 0;
}