#include<iostream>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cstring>
#include<array>
using namespace std;
const int N = 2e5 + 10;
int a[N];
void svole()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int sum=0,ans=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1')
        {
            ans++;
            sum++;
            a[i]=sum;
        }
        else
        {
            sum=0;
            a[i]=sum;
        }
    }
    int f=N;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='0'&&(i==0||i==n-1))
        {
            cout<<ans<<'\n';
            return;
        }
        else if(s[i]=='0')
        {
            f=min(a[i-1],min(a[i+1],f));
        }
    }
    cout<<ans+f<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        svole();
    }
}