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
#include <bits/stdc++.h>
using namespace std;

int sum(map<int, int, greater<int>>& v, int k) {
	int r = 0;
	for (auto e: v) {
		while(e.second--) {
			if (e.first - k <= 0)
				return r;
			r += max(1, e.first - k - 1);
			k += 4;
		}
	}
	return r;
}
 
int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t, n, l, r, p;
    string s;
    map<int, int, greater<int>> v;
    cin >> t;
    while(t--) {
		v.clear();
		cin >> n;
		cin >> s;
		r = 0; p = 0;
		while(p < n && s[p] == '0')
			r += (s[p++] == '0');
		l = r; r = 0;
		while(++p < n) {
			if(s[p] == '0')
				r++;
			else if(r != 0) {
				v[r]++;
				r = 0;
			}
		}
		if (r > l)
			swap(l, r);
		cout << n - max(l + r - 1 + sum(v, 4), max(l + sum(v, 2), sum(v, 0))) << endl;
	}
    return 0;
}