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
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int t;
	cin >> t;
	while (t--) {
		int n, res = 0;
		cin >> n;

		vector <pair<bool, int>> v;
		char prev = '1';
		int cnt = 0;
		int wasone = 0;
		for (int i = 0; i < n; i++) {
			char b;
			cin >> b;
			if (b == '1')
				wasone++;
			if (b == '0') {
				cnt++;
				prev = '0';
			}
			else if (b == '1' && prev == '0') {
				v.push_back({ (v.size() == 0 && !(wasone - 1)), cnt });
				cnt = 0;
				prev = '1';
			}
		}


		if (cnt)
			v.push_back({ 1,  cnt });


		//po ilosci 0
		sort(v.begin(), v.end(), [&](pair<bool, int> a, pair<bool, int> b) { return a.second > b.second; });
			
		int temp = 0;
		//runds passed
		for (int i = 0; i < v.size(); i++) {
			if (v[i].second - temp * (!v[i].first + 1) > 0) {
				res += v[i].second - temp * (!v[i].first + 1);

				if (!v[i].first && (v[i].second - temp * (!v[i].first + 1)) != 1)
					res--;

				temp += 2;
				temp -= v[i].first;
			}

		}
		int tempans = n;

		if (wasone)
			tempans -= res;
		else
			tempans = 0;

		int minans = INT_MAX;
		minans = min(minans, tempans);


		//wpierw brzegi
		sort(v.rbegin(), v.rend());
		temp = 0;
		res = 0;
		//runds passed
		for (int i = 0; i < v.size(); i++) {
			if (v[i].second - temp * (!v[i].first + 1) > 0) {
				res += v[i].second - temp * (!v[i].first + 1);

				if (!v[i].first && (v[i].second - temp * (!v[i].first + 1)) != 1)
					res--;
				else if (!v[i].first)
					temp--;

				temp += 2;
				temp -= v[i].first;
			}

		}

		tempans = n;
		if (wasone)
			tempans -= res;
		else
			tempans = 0;

		minans = min(minans, tempans);

		//jeden brzeg

		temp = 0;
		res = 0;
		for (int i = 0; i < v.size(); i++) {
			if (i == 1 && v[i].first)
				continue;

			if (v[i].second - temp * (!v[i].first + 1) > 0) {
				res += v[i].second - temp * (!v[i].first + 1);

				if (!v[i].first && (v[i].second - temp * (!v[i].first + 1)) != 1)
					res--;
				else if (!v[i].first)
					temp--;

				temp += 2;
				temp -= v[i].first;
			}

		}

		tempans = n;
		if (wasone)
			tempans -= res;
		else
			tempans = 0;

		cout << min (minans, tempans) << "\n";
	}
}