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
#include <stdio.h>
#include <stdlib.h>

struct range {
	int len;
	int type;
};

char text[100001];
struct range ranges[50000];

int make_ranges(int n)
{
	int r = 0;
	int i = 0;

	while (i < n && text[i] == '0')
		i++;
	if (i == n) {
		ranges[r].len = n;
		ranges[r].type = 0;
		return 1;
	} else if (i > 0) {
		ranges[r].len = i;
		ranges[r].type = 1;
		r++;
	}
	ranges[r].len = 0;
	
	for (; i < n; i++) {
		if (text[i] == '0') {
			ranges[r].len++;
		} else if (ranges[r].len > 0) {
			ranges[r].type = 2;
			r++;
			ranges[r].len = 0;
		}
	}
	if (ranges[r].len > 0) {
		ranges[r].type = 1;
		r++;
	}

	return r;
}

int cmp(const void *a, const void *b)
{
	struct range *ra = (struct range *)a;
	struct range *rb = (struct range *)b;

	return rb->len * ra->type - ra->len * rb->type;
}

void test(void)
{
	int n, r;
	int saved = 0;
	int turns = 0;
	int i;

	scanf("%d%s", &n, text);
	r = make_ranges(n);
	qsort(ranges, r, sizeof(ranges[0]), cmp);

	for (i = 0; i < r; i++) {
		ranges[i].len -= turns * ranges[i].type;
		while (ranges[i].len > 0 && ranges[i].type) {
			ranges[i].len--;
			ranges[i].type--;
			turns++;
			saved++;
			if (ranges[i].type)
				ranges[i].len--;
		}
		if (ranges[i].len > 0)
			saved += ranges[i].len;
	}
	printf("%d\n", n - saved);
}

int main(void)
{
	int t;

	scanf("%d", &t);
	while (t--)
		test();
}