#include <bits/stdc++.h>
//#define int long long
using namespace std;
int n, T, a[1000010], f[1000010];
int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c != EOF and !isdigit(c))
	{
		if(c == '-')f = -1;
		c = getchar();
	}
	while(isdigit(c))
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}
int lowbit(int x){
	return x & (-x);
}
string s;
bool vis[1000010];
vector<int>l[1000010];
void dfs(int u, int fa)
{
	vis[u] = 1;
	int x = 0, x2 = 0;
	for(int i = 0;i < l[u].size();i ++)
	{
		int v = l[u][i];
		if(v == fa)continue;
		dfs(v, u);
		if(f[v] and a[v])x ++;
		f[u] += f[v];
	}
	if(a[u])
	{
		if(x == 0)f[u] ++;
	}
	else 
	{
		if(x == 1)f[u] ++;
	}
}
signed main()
{
	T = read();
	while(T --)
	{
		n = read();
		int cnt = 0;
		cin>>s;
		for(int i = 1;i <= n;i ++)
		{
			a[i] = s[i - 1] - '0';
		}
		for(int i = 1;i <= n;i ++)
		{
			int x = i + lowbit(i);
			l[i].push_back(x);
			l[x].push_back(i);
		}
		for(int i = n;i >= 1;i --)
		{
			if(! vis[i])
			{
				dfs(i, -1);
				cnt += f[i];
			}
		}
		cout<<cnt<<endl;
		for(int i = 0;i <= n;i ++)
		{
			vis[i] = a[i] = f[i] = 0;
			l[i].clear();
		}
	}
	return 0;
}