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
#include <bits/stdc++.h>
#define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cerr<<#x<<" "<<x<<endl
#define ll long long 
#define st first
#define nd second
using namespace std;

int n, t, czy, dl, odj, val, rodzaj, res;
string s;
priority_queue <pair<int, int>> pq;
int main()
{
	qio;
	cin >> t;

	for (int i = 1; i <= t; i++) {
		cin >> n;
		cin >> s;
		czy = 0;
		dl = 0;
		for (int j = 0; j < n; j++) {
			if (s[j] == '0') dl++;
			else {
				if (dl > 0) {
					if (czy == 0) {
						pq.push({ dl * 2,1 });
					}
					else {
						pq.push({ dl,2 });
					}
				}
				czy = 1;
				dl = 0;
			}
		}
		if (dl > 0) {
			pq.push({ dl * 2,1 });
		}
		odj = 0;
		res = 0;
		while (!pq.empty()) {
			val = pq.top().st;
			rodzaj = pq.top().nd;
			pq.pop();
			if (rodzaj == 1) {
				res += max(0, val / 2 - odj);
				odj++;
			}
			else {
				if (val - odj * 2 == 1 || val - odj * 2 == 2) {
					res++;
					odj++;
				}
				else {
					res += max(0, val - odj * 2 - 1);
					odj += 2;
				}
			}
		}
		cout << n - res << endl;
	}

}