\(f(L,R)\) を「 \(S\) の \(L\) 文字目から \(R-1\) 文字目までを 1 に、それ以外を 0 にするのに必要な操作回数」とします。 \((L,R)\) 全てに対する \(f(L,R)\) の最小値がこの問題の答えとなります。

\(A_i\) を \(S\) の \(i\) 文字目から \(N\) 文字目までに含まれる 1 の個数とします。このとき、 \(f(L,R)=R-L-2(A_r-A_l)+A_1\) と表せます。

この式より、 \(f\) は Monge 性を持つことが分かります。したがって、 monotone minima を用いることでこの問題は計算量 \(O(N\log N)\) で解くことができます。

実装例(Python3)

for _ in range(int(input())):
    n = int(input())
    s = input()
    a = [0] * (n + 1)
    for i in reversed(range(n)):
        a[i] = a[i + 1] + (s[i] == "1")
    ans = n

    def f(l, r):
        global ans
        if l > r:
            return n
        res = r - l - 2 * (a[l] - a[r]) + a[0]
        ans = min(ans, res)
        return res

    def g(lx, rx, ly, ry):
        if lx >= rx or ly >= ry:
            return
        tyx = (lx + rx) >> 1
        best, idx = n + 1, -1
        for i in range(ly, ry):
            fval = f(tyx, i)
            if best > fval:
                best = fval
                idx = i
        g(lx, tyx, ly, idx + 1)
        g(tyx + 1, rx, idx, ry)

    g(0, n, 0, n + 1)
    print(ans)