You are given a binary string$$$^{\text{∗}}$$$ $$$s$$$ of length $$$n$$$ and you are allowed to perform the following operation any number of times (including zero):

Choose $$$3$$$ indices $$$1 \le i \lt j \lt k \le n$$$ and right shift or left shift the values on $$$s_i$$$, $$$s_j$$$, $$$s_k$$$ cyclically.

For the binary string 110110, if we choose $$$i=1$$$, $$$j=2$$$, $$$k=3$$$ and perform a right shift cyclically, the string becomes 011110; if we choose $$$i=4$$$, $$$j=5$$$, $$$k=6$$$ and perform a left shift cyclically, the string becomes 110101.

Determine the minimum number of operations required to sort the given binary string.

$$$^{\text{∗}}$$$A binary string is a string that consists only of the characters 0 and 1.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 100$$$) — the length of the string.

The second line contains a binary string $$$s$$$ of length $$$n$$$.

Output

For each test case, output a single integer — the minimum number of operations required to sort the given binary string.

Note

For the first test case, the given string is already sorted. So, no operations are needed.

For the second test case, we can choose $$$i = 1$$$, $$$j = 2$$$, $$$k = 4$$$ and perform a right shift cyclically. The string becomes equal to 0011, which is sorted.

Shift Sort

Examples