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 <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct node{
	int val;
	int mul;
};

bool compareNodes(node a, node b){
	return a.val * 2 / a.mul > b.val * 2 / b.mul;
}

int countSickCities(vector<node>& nodes){
	sort(nodes.begin(), nodes.end(), compareNodes);
	int healthy_count = 0;
	int day = 0;
	for(int i = 0; i < nodes.size(); i++){
		int healthy_part_until_that_day = nodes[i].val - day * nodes[i].mul;
		int healthy_part = healthy_part_until_that_day == 1 ? healthy_part_until_that_day : healthy_part_until_that_day - nodes[i].mul + 1;
		if(healthy_part <= 0) {
			break;
		}
		healthy_count += healthy_part;
		day += nodes[i].mul;
	}
	return healthy_count;
}

void do_test_case(){
	int n;
	char city;
	vector<node> nodes;
	node cur = {0, 1} ;
	cin >> n;
	for( int i = 0; i < n; i++){
		cin >> city;
		if(city == '1'){
			nodes.push_back(cur);
			cur = {0,2};
		}
		else {
			cur.val ++;
		}
	}
	if(nodes.empty()) cout << 0 << endl;
	else {
		nodes.push_back({cur.val, 1});
		int healthy_cities = countSickCities(nodes);
		cout << n - healthy_cities << endl;
	}
}

int main(){
	int t;
	cin >> t;
	for(int i = 0; i < t; i++){
		do_test_case();
	}
	
}