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
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto & i : (a))
#define SZ(x) ((int)(x).size())
#define X first
#define Y second
#define PR std::pair
#define MP std::make_pair
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

void parse(const std::string& s, VI& fs, VI& sc){
	int have = 0;
	TRAV(i, s){
		if(i == '0'){
			have++;
		}else{
			if(fs.empty()) fs.push_back(have);
			else sc.push_back(have);
			have = 0;
		}
	}
	fs.push_back(have);
}

void solve(){
	int n;
	std::string s;
	std::cin >> n >> s;

	if(*std::max_element(s.begin(), s.end()) == '0'){
		std::cout << 0 << "\n";
		return;
	}

	VI fs, sc;
	parse(s, fs, sc);
	assert(SZ(fs) == 2);

	std::sort(sc.begin(), sc.end());
	std::reverse(sc.begin(), sc.end());

	int ans = n;
	FOR(mask, 4){
		int cur = n;
		int nw = 0;
		FOR(i, 2) if(mask & (1<<i)) cur -= fs[i] - nw++;
		int i = 0;
		while(i < SZ(sc) && sc[i] - (2 * nw + 1) > 0){
			cur -= sc[i] - (2 * nw + 1);
			nw += 2;
			++i;
		}
		while(i < SZ(sc) && sc[i] - (2 * nw) > 0) {
			cur--;
			nw++;
			++i;
		}

		ans = std::min(ans, cur);
	}

	std::cout << ans << "\n";
}

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

	int t;
	std::cin >> t;
	while(t--) solve();

	return 0;
}