#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N = 2e5 + 7;
int arr[200005];
void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int sum = 0;
    int kk = 1e12, flag = 0;
    //memset(arr, 0, sizeof(arr));
    int op = 0;
    for (int i = 1; i <= s.length(); i++)
    {
        if (i >= 2 && s[i - 1] == '0' && s[i - 2] == '0')
            flag = 1;
        if (s[i - 1] == '0') {
            kk = min(kk, op);
            op = 0;
        }
        else op++, sum++;
    }
    if (s[0] == '0' || s[n - 1] == '0') {
        cout << sum << endl;
    }
    else if (flag)cout << sum << endl;
    else cout << sum + kk << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t; while (t--) solve();
    return 0;
}