#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
const int N=300005;
const ll mod=998244353;
ll qpow(ll a,ll b){
	ll ans=1;
	if(b==0)
	return 1;
	if(b%2)
	ans=a;
	ll t=qpow(a,b/2);
	return t*t%mod*ans%mod;
}
ll inv(ll a){
	return qpow(a,mod-2);
}
void solve(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int cnt=0;
	int cur=0;
	int mn=n;
	for(int i=0;i<n;i++){
	
		if(s[i]=='1'){
			cur++;
			cnt++;
		}
		if(i==n-1||s[i+1]=='0'){
			mn=min(mn,cur);
		}
	}
	if(cnt==0){
		cout<<0<<'\n';
	}
	else if(s[0]=='0'||s[n-1]=='0'){
		cout<<cnt<<'\n';
	}
	else{
		cout<<cnt+mn<<'\n';
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t0;
	cin>>t0;
	for(int t=0;t<t0;t++){
		solve();
	}
}