全ての文字を 0 にするための操作回数の最小値について考えます（全ての文字を 1 にする場合についても同様です）。

まず、元々 1 である文字に対しては少なくとも \(1\) 回以上操作を行う必要があります（ある文字を削除して反転・挿入し直すことを、この文字に対して操作を行うと表現します）。元々 0 である文字に対しては、偶数回の操作を行う必要があるため、\(1\) 回も操作しないか、あるいは \(2\) 回以上の操作を行う必要があります。

元々 0 である文字のうち、その文字に対して \(1\) 回も操作を行わないようなものが最大で何個取れるか考えてみましょう。元々 \(i, j\ (i < j)\) 文字目にあった \(2\) 文字のいずれに対しても \(1\) 回も操作を行わない場合、それらの間にある \(i+1,\dots,j-1\) 文字目についても \(1\) 回も操作を行うことができません。ゆえに、\(1\) 回も操作を行わないような 0 たちは元の文字列において連続した区間をなしている必要があります。

よって、元の文字列における 0 の個数を \(C_0\)、0 が連続して現れる個数の最大値を \(M_0\) とおくと、\(C_0-M_0\) 個の 0 に対しては少なくとも \(2\) 回操作を行う必要があり、\(N-C_0\) 個ある 1 に対しては少なくとも \(1\) 回操作を行う必要があるため、答えは \(2(C_0-M_0)+(N-C_0)\) 以上になります。

逆に、\(2(C_0-M_0)+(N-C_0)\) 回の操作で全ての文字を 0 にすることが常に可能です。詳細は省略しますが、例えば、0 が \(M_0\) 個並ぶ区間の両側にある文字に対して \(1\) 回ずつ操作を行うことでまず 0...01...1 の形に持っていき、その後 \(C_0-M_0\) 個の（元々 0 であった）1 に対して \(1\) 回ずつ操作を行うことで全ての文字を 0 にすることが可能です。

\(C_0,M_0\) の値は \(O(N)\) で求めることができるため、全体の計算量は \(O(N)\) です。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

int solve(int n, string s) {
    vector<int> mx(2), cnt(2);
    for (int l = 0; l < n;) {
        int r = l + 1;
        while (r < n and s[l] == s[r]) ++r;
        int c = s[l] - '0';
        int len = r - l;
        mx[c] = max(mx[c], len);
        cnt[c] += len;
        l = r;
    }
    int ans = 2 * n;
    for (int i = 0; i < 2; i++) {
        ans = min(ans, (cnt[i] - mx[i]) * 2 + cnt[i ^ 1]);
    }
    return ans;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        cout << solve(n, s) << '\n';
    }
}