#include <bits/stdc++.h>
#define all(a) begin(a), end(a)
#define sz(a) (int) (a).size();
#define int long long
using namespace std;

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    bool extra = s.front() == '1' && s.back() == '1';
    vector<int> cts, cts2; int prv = -1, cnt = 0;
    for (auto c : s) {
        if (prv == c) {
            cnt++;
        } else {
            if (prv == '0') cts.push_back(cnt);
            else cts2.push_back(cnt);
            cnt = 1; prv = c;
        }
    }
    if (prv == '0') cts.push_back(cnt);
    else cts2.push_back(cnt);
    extra &= *max_element(all(cts)) == 1;
    int ans = count(all(s), '1') + (extra ? *min_element(all(cts2)) : 0);
    cout << ans << '\n';
}

int32_t main(){
    cin.tie(0); cout.tie(0)->sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        solve();
    }
}