求hack408ABC_D

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5 + 10;

char a[N];
int b[N];
int pre[N];
int rp[N];
int pre1[N];
int rp1[N];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937_64 mrand(time(0));

	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		cin >> a + 1;
		int tot = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] == '1') {
				int len = 0;
				int j = i;
				for (; j <= n; j++) {
					if (a[j] != '1')break;
					len ++;
				}
				b[++tot] = len;
				i = j - 1;
			} else {
				int len = 0;
				int j = i;
				for (; j <= n; j++) {
					if (a[j] != '0')break;
					len ++;
				}
				b[++tot] = -len;
				i = j - 1;
			}
		}
//		cout << "st" << endl;
//		for (int i = 1; i <= tot; i++)cout << b[i] << ' ';
//		cout << endl;
//		if (tot <= 2) {
//			cout << 0 << '\n';
//			continue;
//		}
		int ans = 1e9;
		for (int i = 1; i <= tot; i++) {
			if (b[i] > 0)pre[i] = b[i] + pre[i - 1];
			else pre[i] = pre[i - 1];
		}
		for (int i = tot; i >= 1; i--) {
			if (b[i] > 0)rp[i] = b[i] + rp[i + 1];
			else rp[i] = rp[i + 1];
		}
		for (int i = 1; i <= tot; i++) {
			if (b[i] < 0)pre1[i] = -b[i] + pre1[i - 1];
			else pre1[i] = pre1[i - 1];
		}
		for (int i = tot; i >= 1; i--) {
			if (b[i] < 0)rp1[i] = -b[i] + rp1[i + 1];
			else rp1[i] = rp1[i + 1];
		}
		for (int i = 1; i <= tot + 1; i++) {
			if (b[i] > 0) {
				ans = min(ans, pre[i - 1] + rp[i + 1]);
				ans = min(ans, pre1[i - 1] + rp1[i + 1]);
				ans = min(ans, pre1[i - 1] + rp[i + 1]);
				ans = min(ans, pre[i - 1] + rp1[i + 1]);
			} else {
				ans = min(ans, pre[i - 1] + rp[i + 1]);
				ans = min(ans, pre1[i - 1] + rp[i + 1]);
				ans = min(ans, pre[i - 1] + rp1[i + 1]);
			}
		}
		cout << ans << '\n';
		for(int i=1;i<=tot;i++)pre[i]=rp[i]=pre1[i]=rp1[i]=0;
	}

	return 0;
}