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
117
118
119
120
121
122
123
124
125
126
127
128
129
// Szymon Rusiecki (07.12.2021)
#include <bits/stdc++.h>

bool foo (int A, int B) {
	return A < B;
}

int main () {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int q;
	std::cin >> q;
	while (q > 0) {
		
		int n;
		std::string input;
		std::cin >> n >> input;
		std::vector<int> que_1;
		std::vector<int> que_2;

		int temp = 0;
		int score = n;
		for (int i = 0, start = 1; i < n; ++i) {
			if (input[i] == '0')
				++temp;
			else {
				if (temp > 0)
					(start == 1) ? que_1.push_back(temp) : que_2.push_back(temp);
				temp = 0;
				start = 0;
			}
		}
		if (temp > 0)
			que_1.push_back(temp);
		
		std::sort(que_1.begin(), que_1.end(), foo);
		std::sort(que_2.begin(), que_2.end(), foo);

		int days = 0;
		int it_1 = que_1.size() - 1;
		int it_2 = que_2.size() - 1;
		int output = 0;
		int maxi = 0;

		//case no sides
		days = 0;
		it_1 = que_1.size() - 1;
		it_2 = que_2.size() - 1;
		output = 0;
		
		while (it_2 >= 0) {
			if (que_2[it_2] - 2 * days > 2) {
				output += que_2[it_2] - 2 * days - 1;
				days += 2;
				--it_2;
			}
			else if (que_2[it_2] - 2 * days > 0) {
				output += 1;
				break;
			}
			else break;
		}
		maxi = std::max(maxi, output);

		//case one side
		days = 0;
		it_1 = que_1.size() - 1;
		it_2 = que_2.size() - 1;
		output = 0;

		if (it_1 < 0)
			goto END;
		
		output += que_1[it_1];
		++days;
		
		while (it_2 >= 0) {
			if (que_2[it_2] - 2 * days > 2) {
				output += que_2[it_2] - 2 * days - 1;
				days += 2;
				--it_2;
			}
			else if (que_2[it_2] - 2 * days > 0) {
				output += 1;
				break;
			}
			else break;
		}
		maxi = std::max(maxi, output);

		//case two sides
		days = 0;
		it_1 = que_1.size() - 1;
		it_2 = que_2.size() - 1;
		output = 0;

		if (it_1 < 1)
			goto END;
		
		output += que_1[it_1--];
		++days;
		output += que_1[it_1] - days;
		++days;
		
		while (it_2 >= 0) {
			if (que_2[it_2] - 2 * days > 2) {
				output += que_2[it_2] - 2 * days - 1;
				days += 2;
				--it_2;
			}
			else if (que_2[it_2] - 2 * days > 0) {
				output += 1;
				break;
			}
			else break;
		}
		maxi = std::max(maxi, output);
		
		END:
		std::cout << score - maxi << '\n';
		--q;


	}

	return 0;
}