#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
using ll = long long;

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

	string s;
	cin >> s;
	vector<int> tr(n + 1);
	auto add = [&](int x, int v) {
		for (int i = x; i <= n; i += i & -i) {
			tr[i] += v;
		}
	};
	auto query = [&](int x) {
		int res = 0;
		for (int i = x; i; i -= i & -i) {
			res += tr[i];
		}
		return res;
	};

	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int v = tr[i + 1];
		if (v > 0 && s[i] != '0') continue;
		if (v == 0 && s[i] != '0') {
			ans++;
			add(i + 1, 1);
		} else if (v > 0 && s[i] == '0') {
			ans += v;
			add(i + 1, -v);
		}
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
    	solve();
    }
	return 0;
}