#include<bits/stdc++.h>
using namespace std;

#define int long long
#define F first 
#define S second
#define pb push_back

const int mol=998244353;
int cnt=0;
int n;
int ca(string a){
    vector<int>ha(n+1, 0);
    for(int i=0;i<a.size();i++){
        if(a[i]=='0') ha[i]=0;
        else{
            if(ha[i-1]) ha[i]=ha[i-1]-1;
            else{
                int t=i;
                while(a[t]=='1') ha[i]++, t++;
            }
        }
    }
    int ans=1e18, cc=0;
    for(int i=0;i<a.size();i++){
        if(a[i]=='1') cc++;
        if(a[i]=='0'){
            ans=min(ans, cnt+ha[i+1]);
        }
    }
    return ans;
}
void solve(){
    cnt=0;
    cin>>n;
    string a;
    cin>>a;
    for(int i=0;i<a.size();i++){
        if(a[i]=='1') cnt++;
    }
    if(a[0]!='1'||a[a.size()-1]!='1'){
        cout<<cnt<<"\n";
        return;
    }
    auto b=a;
    reverse(b.begin(), b.end());
    cout<<ca(b)<<"\n";
    return;
    int ans=min(ca(a), ca(b));
    
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}