#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define fi first
#define se second
void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<pii>ar;
    int mn = 0x3f3f3f3f,sum = 0;
    for(int i = 0;i < (int)s.size();i ++)
    {
        int j = i;
        while(j + 1 < (int)s.size() && s[j + 1] == s[i])
            j ++;
        ar.push_back({s[i] - '0',j - i + 1});
        if(s[i] - '0' == 1)
            mn = min(mn,j - i + 1),sum += j - i + 1;
        i = j;
    }
    if(ar[0].fi == 1 && ar.back().fi == 1){
        if(mn == 0x3f3f3f3f)
            cout<<"0\n";
        else
            cout<<sum + mn<<"\n";
    }
    else
        cout<<sum<<"\n";
    

}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    cin>>T;
    while(T --)
        solve();
}