A. Shift Sort
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
4
3
001
4
0110
6
110100
6
101011
Output
0
1
2
1
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.