#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(void)
{
	int t;
	cin>>t;
	while(t--){
		int n;
		string s;
		cin>>n>>s;
		int a[n+1],ans=0;
		for(int i=1;i<=n;i++){
			a[i]=s[i-1]-'0';
			if(a[i]==1) ans++;
		}
		int num1=0,num2=0;
		if(a[1]==1&&a[n]==1){
			for(int i=1;i<=n;i++){
				if(a[i]==1) num1++;
				else{
					if(i<=n-1&&a[i+1]==0) num1=0;
					break;
				}
			}
			for(int i=n;i>=1;i--){
				if(a[i]==1) num2++;
				else{
					if(i>=2&&a[i-1]==0) num2=0;
					break;
				}
			}
		}
		int posl,posr,minn=n,tag=0,cnt=0;
		for(int i=1;i<=n;i++){
			if(a[i]==1&&tag==0) tag=1,cnt++,posl=i;
			else if(a[i]==1&&tag==1) cnt++;
			else if(a[i]==0&&tag==1){
				tag=0,posr=i-1;
				if(posl>=3&&a[posl-2]==1&&posr<=n-2&&a[posr+2]==1) minn=min(minn,cnt);
				cnt=0;
			}
		}
		if(minn==n) minn=0;
		if(num1&&num2){
			if(minn==0) ans+=min(num1,num2);
			else ans+=min(minn,min(num1,num2));
		}
		cout<<ans<<endl;
	}
	return 0;
}