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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int t;
int n;
char S[N];

bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.first != b.first) {
		return a.first > b.first;
	}
	if (b.second == 0) {
		return false;
	}
	if (a.second == 0) {
		return true;
	}
	return a.second > b.second;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		scanf("%s", &S);
		vector<pair<int, int> > order;
		int l = -1;
		for (int i = 0; i < n; i++) {
			if (S[i] == '1') {
				l = i;
				break;
			}
		}
		if (l == -1) {
			printf("0\n");
			continue;
		}
		int r = n + 1;
		for (int i = n - 1; i >= 0; i--) {
			if (S[i] == '1') {
				r = i;
				break;
			}
		}
		int op = 0;
		if (l > 0) {
			order.push_back(make_pair(l, 0));
			op++;
		}
		if (r < n - 1) {
			order.push_back(make_pair(n - r - 1, 0));
			op++;
		}
		int curr = 0;
		pair<int, int> p;
		for (int i = l + 1; i <= r; i++) {
			if (S[i] == '0') {
				curr++;
			}
			else if (curr > 0) {
				p = make_pair((curr / 2) + (curr & 1), curr / 2);
				p.first = curr / 2;
				p.second = p.first;
				if (curr & 1) {
					p.first++;
				}
				order.push_back(p);
				op += 1 + (curr != 1);
				curr = 0;
			}
		}
		sort(order.begin(), order.end(), cmp);
		l = 0, r = order.size() - 1;
		int res = 0;
		int f = 0;

		while (l <= r) {
			op--;
			int ile = order[l].first;
			order[l].first = 0;
			swap(order[l].first, order[l].second);
			if (order[l].first > 0) {
				order[l].first += ile - f - 1;
			}
			if (order[l].first <= f) {
				if (order[l].first > 0) {
					op--;
				}
				l++;
			}
			while (l <= r && order[r].first <= f) {
				r--;
			}
			while (l <= r && order[r].first == f + 1) {
				res++;
				op--;
				if (order[r].second == f + 1) {
					res++;
				}
				if (order[r].second > 0) {
					op--;
				}
				r--;
			}
			res += op;
			f++;
		}
		for (int i = 0; i < n; i++) {
			res += S[i] == '1';
		}
		
		printf("%d\n", res);
	}
}