You have a binary string S. You can perform the following operation on S:
Select any substring $S_{L \dots R} (1$ ≤ L ≤ R ≤ |S|) which is sorted in non-decreasing order and remove it from S.
(Both the left and right halves are concatenated after performing the operation)

For e.g. if S = 100011000, we can perform the following operation: $100\underline{011}000 \rightarrow 100000$

Find the minimum number of operations required so that the final binary string S is sorted in non-decreasing order.

Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.

------ Input Format ------

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N — the length of the binary string S.
• The second line of each test case contains a binary string S of length N containing 0s and 1s only.

------ Output Format ------

For each test case, output the minimum number of operations required so that the final binary string S is sorted in non-decreasing order.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$S$ contains $0$ and $1$ only.
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
3
3
000
5
01110
2
10

----- Sample Output 1 ------
0
1
1

----- explanation 1 ------
Test case $1$: The binary string is already sorted, so we need no operations.

Test case $2$: We can use one operation to remove the sorted substring $S_{2 \dots 4} = 111$. Thus, the remaining string $00$ is sorted.

Test case $3$: We can use one operation to remove the sorted substring $S_{2 \dots 2} = 0$. Thus, the remaining string $1$ is sorted.

见题面

见题面