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
#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;
 
const int MAX_N = 1e6+5;
const int M = 3e4+5;
const ll INF = (ll)(1e18);
const int inf = 1e9;
const ll MOD = 1000000007LL;

void solve() {
	int n; string s;
	cin >> n >> s;
	
	multiset<int> one;
	vector<int> two;
	int l = 0;
	int cnt_ones = 0;
	while (l < n) {
		if (s[l] == '1') {
			l++;
			cnt_ones++;
			continue;
		}
		
		int r = l;
		while (r < n && s[r] == '0') r++;

		if (l == 0 || r == n) one.insert(r - l);
		else two.push_back(r - l);

		l = r;
	}
	
	if (cnt_ones == 0) {
		cout << "0\n";
		return;
	}
	
	sort(two.begin(), two.end());
	int time = 0;
	int saved = 0;
	
	while (true) {
		//cout<<"\n\ntime: "<<time<<endl;
		int best_one = -1, best_two = -1;
		if (!two.empty()) best_two = two.back() - 2*time;
		if (!one.empty()) best_one = *one.rbegin() - time;
		
		//cout<<"best_one: "<<best_one<<endl;
		//cout<<"brdt_two: "<<best_two<<endl;
		if (best_one <= 0 && best_two <= 0) break;
		
		if (best_one >= best_two - 2 && best_one > 0) {
			//cout<<"CHOSE BEST_ONE"<<endl;
			//cout << time << ": " << best_one << '\n';
			saved += best_one;
			one.erase(one.find(best_one + time));
		} else {
			//cout<<"CHOSE BEST_two"<<endl;

			//cout << time << ": " << best_two << '\n';
			two.pop_back();
			saved++;
			one.insert(best_two + time - 1);
		} 
		
		time++;
	}
	
	cout << n - saved << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
			
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	

	
    return 0;
}