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
#include <bits/stdc++.h>

const int MAXN = 100005;

char t[MAXN];
int buckets[MAXN];

void answer(int ans) {
	printf("%d\n", ans);
}

int get_score(const std::vector<int> &v, int left, int right, int take_left, int take_right) {
	int iter = 0;
	int score = 0;
	
	if (take_left) {
		score += left;
		iter++;
	}
	
	if (take_right) {
		score += std::max(0, right-iter);
		iter++;
	}
	
	for (int i=v.size()-1; i>=0; i--) {
// 		printf("ccc %d %d, %d %d\n", i, v[i], iter, score);
		if (v[i] <= 2*iter)
			return score;
		if (v[i] == 2*iter + 1)
			return score + 1;
		score += v[i] - 2*iter - 1;
		iter += 2;
	}
	
	return score;
}

void solve() {
	int n;
	scanf("%d", &n);
	scanf("%s", t);
	
	int left = 0;
	for (int i=0; i<n; i++) {
		if (t[i] == '0')
			left++;
		else
			break;
	}
	
	if (left == n)
		return answer(0);
	
	int right = 0;
	for (int i=n-1; i>=0; i--) {
		if (t[i] == '0')
			right++;
		else
			break;
	}
	
	int begin_idx = 0;
	std::vector<int> v;
	
	for (int i=left; i<n-1; i++) {
		if (t[i] == '1' && t[i+1] == '0')
			begin_idx = i;
		if (t[i] == '0' && t[i+1] == '1') {
			// found i-begin_idx
			buckets[i-begin_idx]++;
		}
	}
	
	for (int i=1; i<=n; i++) {
		for (int x=0; x<buckets[i]; x++)
			v.push_back(i);
		buckets[i] = 0;
	}
	
// 	printf("left %d right %d\n", left, right);
	
	int sc = 0;
	
	if (right > left)
		std::swap(right, left);  // now left is bigger
	
	for (int take_left=0; take_left<2; take_left++) {
		for (int take_right=0; take_right<=take_left; take_right++) {
			if (take_left && left == 0)
				continue;
			if (take_right && right == 0)
				continue;
			
			int tmp = get_score(v, left, right, take_left, take_right);
			
// 			printf("aaa %d %d %d\n", take_left, take_right, tmp);
			
			sc = std::max(sc, tmp);
		}
	}
	
	answer(n-sc);
}

int main() {
	int T;
	scanf("%d", &T);
	
	while (T--) {
		solve();
	}
	
	return 0;
}