1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#ifdef LOC
#include "debuglib.h"
#else
#define deb(...)
#define DBP(...)
#endif
using namespace std;
using   ll         = long long;
using   Vi         = vector<int>;
using   Pii        = pair<int, int>;
#define pb           push_back
#define mp           make_pair
#define x            first
#define y            second
#define rep(i, b, e) for (int i = (b); i < (e); i++)
#define each(a, x)   for (auto& a : (x))
#define all(x)       (x).begin(), (x).end()
#define sz(x)        int((x).size())

ll pref(ll n) { return n*(n+1) / 2; }

int findSingleTwo(const Vi& groups, int numOnes) {
	int b = 0, e = sz(groups)+1;
	while (b+1 < e) {
		int m = (b+e) / 2;
		(groups[m-1] > (m+numOnes-1)*2 ? b : e) = m;
	}
	return b;
}

int solve(const Vi& groups, const Vi& side) {
	priority_queue<int, vector<int>, greater<int>> ones;
	int onesSum = 0, twosCount = 0;
	int ans = 0;

	each(e, side) {
		ones.push(e);
		onesSum += e;
	}

	auto update = [&]() {
		while (!ones.empty() && ones.top() <= twosCount+sz(ones)-1) {
			onesSum -= ones.top();
			ones.pop();
		}
		int singleTwoEnd = findSingleTwo(groups, sz(ones));
		int onesDecay = int(pref(twosCount+sz(ones)-1) - pref(twosCount-1));
		ans = max(ans, twosCount + onesSum - onesDecay + max(singleTwoEnd-twosCount, 0));
	};

	update();

	each(e, groups) {
		int rem = e - twosCount*2;
		if (rem <= 0) break;
		int tmp = rem + twosCount - 1;
		ones.push(tmp);
		onesSum += tmp;
		twosCount++;
		update();
	}

	return ans;
}

int run() {
	int n;
	string s;
	cin >> n >> s;

	int left = int(find(all(s), '1') - s.begin());
	if (left >= n) {
		return 0;
	}

	int last = left;
	Vi groups;

	rep(i, left+1, n) {
		if (s[i] == '1') {
			if (i-last-1 > 0) groups.pb(i-last-1);
			last = i;
		}
	}

	int right = n-last-1;
	sort(all(groups), greater<int>());

	Vi side;
	if (left > 0) side.pb(left);
	if (right > 0) side.pb(right);
	return n - solve(groups, side);
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(12);
	int t; cin >> t;
	while (t--) cout << run() << '\n';
	return 0;
}