A. Shift Sorttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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 < j < 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.InputEach 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$$$.OutputFor each test case, output a single integer — the minimum number of operations required to sort the given binary string.ExampleInput430014011061101006101011Output0
1
2
1
NoteFor 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.