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
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

string s;
vector<int>vctr;
vector<int>extra;
int k[4];
int res[4];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, t, pref, suf, lst, res, k, R;
	cin >> t;
	
	while(t--){
		cin >> n >> s;
		lst = -1;
		
		for(int i=0; i<n; i++){
			if(s[i] == '0') continue;
			if(lst != i-1){
				if(lst == -1) extra.push_back(i - lst - 1);
				else vctr.push_back(i - lst - 1);
			}
			lst = i;
		}
		
		if(lst != n-1) extra.push_back(n - lst - 1);
		
		while(extra.size() < 2) extra.push_back(0);
		
		sort(vctr.begin(), vctr.end());
		reverse(vctr.begin(), vctr.end());
		sort(extra.begin(), extra.end());
		reverse(extra.begin(), extra.end());

		R = 0;
		for(int i=0; i<=3; i++){
			res = k = 0;
			
			for(int j=0; j<=1; j++){
				if(!((1<<j)&i)) continue;
				if(extra[j] - k > 0){
					res += extra[j] - k;
					k++;
				}
			}
			
			for(auto w:vctr){
				if(w - k - k >= 2){
					res += w - k - k - 1;
					k += 2;
				}
				else if(w - k - k == 1){
					res++;
					k++;
				}
				else break;
			}
			
			
			for(int j=0; j<=1; j++){
				if((1<<j)&i) continue;		
				if(extra[j] - k > 0){
					res += extra[j] - k;
					k++;
				}		
			}
			
			R = max(R, res);
		}
		
		cout << n - R << '\n';
		
		vctr.clear();
		extra.clear();
	}
	
	return 0;
}