2085: Alban's Jedi Lightsaber Power Calibration

In Jedi training, Alban needs to calibrate his lightsaber's energy distribution. The lightsaber has $N$ energy nodes, each either in an active state (represented by 1) or a dormant state (represented by 0).

Alban can perform the following operation any number of times (including zero):

• Choose a node $i$ ($1 \leq i \leq N$) and flip its state (active becomes dormant, dormant becomes active).

His goal is to make all active nodes form at most one contiguous block, so the lightsaber's energy flow will be more stable. Find the minimum number of operations required to achieve this goal.

More precisely, the goal is for there to exist a pair of integers $(l, r)$ that simultaneously satisfies:

1. $1 \leq l \leq r \leq N + 1$

2. For every integer $i$ satisfying $1 \leq i \leq N$, node $i$ is active if and only if $l \leq i < r$

The Force indicates that this goal can always be achieved in a finite number of operations.

Given $T$ test cases, please help Alban solve each one.

Constraints

• $1 \leq T \leq 20000$

• $1 \leq N \leq 2 \times 10^5$

• $S$ is a string of length $N$ consisting of 0 and 1

• For each input file, the sum of $N$ over all test cases does not exceed $2 \times 10^5$

• $T$ and $N$ are integers

Input is given from Standard Input in the following format:

Each test case $case_i$ is in the following format:

Output $T$ lines. The $i$-th line ($1 \leq i \leq T$) should contain the answer to the $i$-th test case.

Output $T$ lines. The $i$-th line ($1 \leq i \leq T$) should contain the answer to the $i$-th test case.