#include<bits/stdc++.h>
using namespace std;
int T;
int n;
string s;
int len[200005],cntl;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>s;
        int cnt=0;
        for(int i=0;i<n;++i) if(s[i]=='1') ++cnt;
        if(s[0]=='0'||s[n-1]=='0'){
            cout<<cnt<<'\n';
        }else{
            bool fl=0;
            for(int i=0;i+1<n;++i)
                if(s[i]=='0'&&s[i+1]==0)
                    fl=1;
            if(fl) cout<<cnt<<'\n';
            else{
                cntl=0;
                for(int i=0,j=i;i<n;i=j+1){
                    if(s[i]=='1'){
                        j=i;
                        while(j+1<n&&s[j+1]=='1') ++j;
                        len[++cntl]=j-i+1;
                    }else j=i;
                }
                int del1=min(len[1],len[2]);
                int del2=min(len[cnt-1],len[cnt]);
                int del=min(del1,del2);
                cout<<cnt+del<<'\n';
            }
        }
    }
    return 0;
}