#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define llt __int128_t
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 1e2+10;
const int M = 1e6 + 7;
const int MAX = 0x3f3f3f3f;
const ll maxn = 1e18;
ll h,s1,vv,u,mi,mx,fz,fm,ans,item,f;
ll m,n,x,y,x2,y2,z,z2,d,gcd,l,r,k,T,p,cnt;
ll sum;
ll c[M],dp[N][N];
string s,ss,s3,s2;
ll a[N];
map<char,ll>mp;
void solve() {
	cin>>n;
	cin>>s;
	l=-1;
	r=0;
	f=1;
	for(ll i=0;i<n;i++){
		if(s[i]=='1'){
			r++;
		}
		else{
			if(r-l==0){
				f=0;
			}
			l=i;
			r=l;
		}
	}
	l=0;
	ll ans=0;
	ll mn=1e10;
	for(ll i=0;i<n;i++){
		if(s[i]=='1'){
			ans++;
			l++;
		}
		else if(l>0){
			mn=min(mn,l);
		}
	}
	if(l>0){
		mn=min(mn,l);
	}
	if(f==1&&s[0]=='1'&&s[n-1]=='1'){
		cout<<ans+mn<<"\n";
	}
	else{
		cout<<ans<<"\n";
	}
}
int main() {
	IOS;
	T=1;
	cin>>T;
	while(T--) {
		solve();
	}
	return 0;
}