#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n; string s;
        cin >> n >> s;
        int ans = count(s.begin(), s.end(), '1');
        int mn = 1e9;
        for(int i = 0; i < n; i++){
            if (s[i] == '0') continue;
            int j = i;
            while(j + 1 < n and s[j + 1] == '1') j++;
            mn = min(mn, j - i + 1);
            i = j;
        }
        bool ok = false;
        for(int i = 0; i < n; i++){
            if (s[i] == '0') continue;
            int j = i;
            while(j + 1 < n and s[j + 1] == '1') j++;
            if (i - 1 >= 0 and s[i - 1] == '0'){
                swap(s[i - 1], s[j]);
            }
            else if (j + 1 < n and s[j + 1] == '0'){
                swap(s[i], s[j + 1]);
            }
            else{
                ok = true;
                break;
            }
            i = j;
        }
        if (ok) ans += mn;
        cout << ans << '\n';
    }

}