P14258 Favor

Little S and Little Y are using $n$ floating boards arranged in a row in the swimming pool. Each board is either face up or face down. They number the boards from front to back as $1$ to $n$. Each time, Little S can choose a board and flip it forward. Due to the water flow generated by the flip, all boards in front of it, including itself, will move forward one position. Then, Little Y will move the originally frontmost float board back to the empty position without flipping it. Specifically, suppose Little S chooses board $i$. Then the boards in front of it are boards $1, \dots, i$. After they all move forward one position, the original board $j$ will move to position $j-1$. In particular, the board now at position $i-1$ is the original board $i$ after being flipped, while the other boards are not flipped. After this, the original board $1$ will move to position $0$, and position $i$ will have an empty spot. Little Y will move this board from position $0$ to position $i$ without flipping it, covering a distance of $i$. Little S wants to know how she should flip the boards so that, while making all boards face the same side up, the total distance Little Y moves the boards is minimized.

**This problem contains multiple test cases.** The first line of input contains a positive integer $T$, representing the number of test cases. This is followed by $T$ test cases, each formatted as follows: The first line contains an integer $n$, indicating the number of float boards. The second line contains $n$ characters $b_1, \dots, b_n$, each of which can only be either $\texttt{0}$ or $\texttt{1}$, indicating the initial state of the float boards. Here, $b_i = \texttt{0}$ indicates that float board $i$ is facing up, and $b_i = \texttt{1}$ indicates that it is facing down.

For each test case, output a single integer in a line indicating the answer.

**【Sample 1 Explanation】** For the first test case, after Little S flips float board $1$, Little Y moves the float board from position $0$ to $1$. At this point, all float boards are facing down, and the total movement distance is $1$. For the second test case, after Little S flips float board $3$, Little Y moves the float board from position $0$ to $3$. At this point, all float boards are facing up, and the total movement distance is $3$. For the third test case, they can proceed with the following steps: 1. Little S flips float board $1$, Little Y moves the float board from $0$ to $1$ (distance $1$). The state of the float boards becomes `0011100`. 2. Little S flips float board $5$, Little Y moves the float board from $0$ to $5$ (distance $5$). The state becomes `0110000`. 3. Little S flips float board $3$, Little Y moves the float board from $0$ to $3$ (distance $3$). The state becomes `1000000`. 4. Little S flips float board $1$, Little Y moves the float board from $0$ to $1$ (distance $1$). The state becomes `0000000`. Finally, all float boards are facing up, with a total movement distance of $1+5+3+1=10$. It can be proven that no solution with a smaller total movement distance exists. **【Sample 2】** See favor2.in and favor2.ans in the problem attachment. This sample satisfies the special properties for test datas 5 and 6. **【Sample 3】** See favor3.in and favor3.ans in the problem attachment. This sample satisfies the special properties for test datas 7 and 8. **【Data Range】** For all test data, it is guaranteed that: $1 \le T \le 5$, $1 \le n \le 10^6$, and $b_i = \texttt{0}$ or $\texttt{1}$. ::cute-table{tuack} | Test Data ID | $n \le$ | Special Property | | :-: | :-: | :-: | | $1,2$ | $10$ | None | | $3,4$ | $10^3$ | Present | | $5,6$ | ^ | None | | $7,8$ | $10^6$ | Present | | $9,10$ | ^ | None | Special Property: There exists a $1 \le k \le n-1$ such that for $1 \le i \le k$, $b_i = \texttt{0}$; and for $k+1 \le i \le n$, $b_i = \texttt{1}$.