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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define all(a) a.begin(),a.end()

void solve(){
	int n; cin >> n;
	string s; cin >> s;
	s = '#'+s;
	s = s+'1';
	int ile1 = 0;
	for(auto c : s) if(c == '1') ile1++;
	if(ile1 == 0){
		cout << "0\n";
		return;
	}
	priority_queue<pair<int,int>> q;
	int p = 1,k = 1;
	while(s[k] == '0') k++;
	if(k > 1) q.push({k-1,2});
	p = k;
	while(k <= n+1){
		if(s[k] == '1'){
			if(k != p && k == n+1){
				q.push({k-p,2});
			}else if(k != p && k != n+1){
				q.push({k-p,1});
			}
			k++;
			p = k;
		}
		else k++;

	}
	// while(q.size() > 0){
	// 	pair<int,int> p = q.top();
	// 	q.pop();
	// 	cout << p.st << " " << p.nd << "\n";
	// }
	int t = 0,urat = 0;
	while(q.size() > 0 && t <= n){
		pair<int,int> p = q.top();
		q.pop();
		if(p.st == 0) continue;
		if(p.nd == 2 && p.st <= t) continue;
		if(p.nd == 1 && p.st <= 2*t) continue;
		if(p.nd == 2){
			urat += p.st-t;
			t++;
		}else{
			urat += max(p.st-2*t-1,0);
			t += 2;
		}
	}
	cout << n-urat << "\n";
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t; cin >> t;
	while(t--) solve();
}