40pts求调

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=1e6+5;
int n,a[N];
string s;
ll solve1(int l,int r,int p){
	ll res=0;
	while(l<=r){
		if(l>1&&a[l-1]==p){
			res+=r;
			a[r]=p;
			a[--l]=(p^1);
			a[--r]=p;
			--r;
		}
		else{
			res+=l;
			a[l++]=p;
		}
	}
	return res;
}
ll solve(int p){
	for(int i=1;i<=n;++i) a[i]=(s[i-1]=='1');
	ll res=0;
	for(int i=1;i<=n;++i){
		int j=i;
		if(a[i]==p) continue;
		while(j<n&&a[j+1]==(p^1)) ++j;
		res+=solve1(i,j,p);
		i=j;
	}
	return res;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    //freopen("favor3.in","r",stdin);
    //freopen("a.out","w",stdout);
    
    int T;
    cin>>T;
    while(T--){
    	cin>>n>>s;
    	cout<<min(solve(0),solve(1))<<'\n';
	}
    return 0;
}