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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define fi first
#define se second

const int N = 100100;

int n, m;
char s[N];
int L[N], L0, L1;
int suff[N];

void solve() {
	scanf("%d %s", &n, s);
	m = 0;
	L0 = L1 = -1;
	int add = 0;
	FOR(i,n) if (s[i] == '1') {
		if (L0 == -1) L0 = i;
		L1 = n-1-i;
		add++;
	}
	if (L0 == -1) {
		printf("0\n");
		return;
	}
	int Lc = 0;
	for (int i = L0; i < n-L1; i++) {
		if (s[i] == '0') {
			Lc++;
		} else {
			if (Lc > 0) {
				L[m++] = -Lc;
			}
			Lc = 0;
		}
	}
	if (L0 < L1) swap(L0, L1);
	L[m++] = -1000000;
	sort(L,L+m);
	FOR(i,m) L[i] = -L[i];
	
	//cerr << "L = " << L0 << " " << L1 << "\nL = ";
	//FOR(i,m) cerr << L[i] << " ";
	//cerr << "\n";
	
	suff[m] = 0;
	for (int i = m-1; i > 0; i--) suff[i] = suff[i+1] + L[i];
	
	int res = n-add;
	FOR(k,m) {
		// 1) t = 2*k
		int t = 2*k;
		if (L[k]>=t*2-1) {
			int sub = 0;
			if (k+1<m && L[k+1]>t*2) sub = 1;
			//cerr << k << " segments in time " << t << " : lowest segment taken = " << L[k] << ", suffix = " << suff[k+1] << "\t:\t " << t*(t-1)/2+L0+L1+suff[k+1] << "\n";
			res = min(res, t*(t-1)/2+L0+L1+suff[k+1]-sub);
		}
		// 2) t = 2*k+1
		t++;
		if (L[k]>=t*2-1 && L0>=t) {
			int sub = 0;
			if (k+1<m && L[k+1]>t*2) sub = 1;
			//cerr << k << " segments + one border in time " << t << " : lowest segment taken = " << L[k] << ", suffix = " << suff[k+1] << "\t:\t " << t*(t-1)/2+L1+suff[k+1] << "\n";
			res = min(res, t*(t-1)/2+L1+suff[k+1]-sub);
		}
		// 3) t = 2*k+2
		t++;
		if (L[k]>=t*2-1 && L1>=t) {
			int sub = 0;
			if (k+1<m && L[k+1]>t*2) sub = 1;
			//cerr << k << " segments + two borders in time " << t << " : lowest segment taken = " << L[k] << ", suffix = " << suff[k+1] << "\t:\t " << t*(t-1)/2+suff[k+1] << "\n";
			res = min(res, t*(t-1)/2+suff[k+1]-sub);
		}
	}
	printf("%d\n", res+add);
}

int main() {
	int tt;
	scanf("%d", &tt);
	FOR(ii,tt) solve();
	return 0;
}