#include <bits/stdc++.h>

#define MULTI int _; cin >> _; while (_--)
#define fi first
#define se second
#define pb(a) push_back(a)
#define rep(i, n) for (int i = 0; i < n; i++)
#define reps(i, n, m) for (int i = n; i <= m; i++)
#define repsv(i, n, m) for (int i = n; i >= m; i--)
#define vsz(a) (int)(a.size())
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()

using namespace std;

typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;

#ifdef LOCAL
#include "debugs.hpp"
#else
#define dbg(...) 0
#endif




void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    vi pos;
    rep(i, n)
        if(s[i] == '0')
            pos.pb(i);
    int ans = INT_MAX;
    // go left
    int cur = 0;
    reps(i, 0, vsz(pos)-2){
        int p = pos[i];
        while(--p >= 0 && s[p] != '0')
            cur++;
    }
    int l = pos.back()-(vsz(pos) == 1 ? 0 : pos[vsz(pos)-2]+1);
    int r = n-1-pos.back();
    dbg(cur, l, r);
    cur += 2*min(l, r)+max(l, r);
    // dbg(cur);
    ans = min(ans, cur);
    // go right
    cur = 0;
    reps(i, 1, vsz(pos)-1){
        int p = pos[i];
        while(++p < n && s[p] != '0')
            cur++;
    }
    l = pos[0];
    r = (vsz(pos) == 1 ? n-1-pos[0] : pos[1]-pos[0]-1);
    dbg(cur, l, r);
    cur += 2*min(l, r)+max(l, r);
    // dbg(cur);
    ans = min(ans, cur);
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    MULTI
    solve();
}