Description

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.

Input Format

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.

Output Format

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

3
2
01
3
001
7
1011100

1
3
10

Hint

【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}

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}$.