#include <bits/stdc++.h>
// #define pii pair<int, int>
#define int long long

using namespace std;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    int sum{};
    for(auto &i : s) sum += (i == '1');

    if (s[0] == '1' && s.back() == '1') {
        bool flag = false;
        for (int i = 1; i < n; i++) {
            if (s[i] == '0' && s[i - 1] == '0') {
                flag = true;
                break;
            }
        }
        if (!flag) {
            int min1 = 3e5, len = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == '1') {
                    len++;

                } else {
                    if (len != 0) {
                        min1 = std::min(min1, len);
                    }
                    len = 0;
                }
            }
            if (len != 0) {
                min1 = std::min(min1, len);
            }
            std::cout << sum + len << '\n';
            return ;
        }
    }

    std::cout << sum << '\n';
}

/*
5
a
sos
abba
icpc
tenet
*/

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
    std::cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }

    return 0;
}