#include <array>
#include <vector>
#include <iostream>

using i64 = long long;

void solve() {
	int n;
	std::cin >> n;

	std::vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) {
		char ch; std::cin >> ch;
		a[i] = (ch - '0');
	}

	std::array<std::vector<int>, 31> pos;
	for (int i = 1; i <= n; i++) pos[std::__lg(i & -i)].push_back(i);

	std::vector<int> b(n + 1, 0); int ans = 0;

	for (int i = 1; i <= n; i += 2) if (a[i] == 1) b[i] = 1, ans++;

	for (int lowbit = 1; lowbit < 31; lowbit++) {
		std::vector<int> sum(n + 1, 0);
		for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];

		for (auto x : pos[lowbit]) {
			if (a[x] == 0 && sum[x] - sum[x - (x & -x)] != 0) {
				b[x] = sum[x - (x & -x)] - sum[x];
				ans++;
			}

			if (a[x] == 1 && sum[x] - sum[x - (x & -x)] == 0) {
				b[x] = 1;
				ans++;
			}
		}
	}

	std::cout << ans << "\n";
}

int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin >> T;

	while (T--) solve();

	return 0;
}