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
94
95
96
97
98
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
using namespace std;

const int N = 100000 + 5;

struct Item {
	int cnt;
	int type;

	bool operator<(const Item &oth) const {
		if (1 == type && 2 == oth.type) {
			return 2 * cnt + 1 <= oth.cnt;
		}
		if (2 == type && 1 == oth.type) {
			return cnt < 2 * oth.cnt + 1;
		}
		return cnt < oth.cnt;
	}
};

int nextInt() { int n; scanf("%d", &n); return n; }
char buf[N];
priority_queue<Item> q;

template <class T>
void myClear(T &container) {
	T empty;
	std::swap(empty, container);
}

int solve(int n) {
	myClear(q);
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		if (buf[i] == '0') {
			int j = i + 1;
			while (j < n && buf[j] == '0') ++j;
			int type = 2;
			if (i == 0 || j == n) type = 1;
			q.push({ j - i, type });
			i = j - 1;
		}
		else {
			++sum;
		}
	}

	if (0 == sum) return 0;
	if (q.empty()) return sum;

	int t = 0;
	while (!q.empty()) {
		int cnt = q.top().cnt;
		int type = q.top().type;
		q.pop();

		int lost = t * type;
		if (lost > cnt) lost = cnt;

		if (lost == cnt) {
			sum += lost;
			continue;
		}
		if (1 == type) {
			sum += lost;
			++t;
			continue;
		}
		if (lost == cnt - 1) {
			sum += lost;
			++t;
			continue;
		}
		sum += t;
		++t;
		q.push({ cnt - t, 1 });
	}

	return sum;
}

int main() {
	int TC = nextInt();

	for (int i = 0; i < TC; ++i) {
		int n = nextInt();
		scanf("%s", buf);
		int res = solve(n);
		printf("%d\n", res);
	}

	return 0;
}