Codeforces Global Round 15 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

sortings

strings

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Subsequence Permutation

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA string $$$s$$$ of length $$$n$$$, consisting of lowercase letters of the English alphabet, is given.

You must choose some number $$$k$$$ between $$$0$$$ and $$$n$$$. Then, you select $$$k$$$ characters of $$$s$$$ and permute them however you want. In this process, the positions of the other $$$n-k$$$ characters remain unchanged. You have to perform this operation exactly once.

For example, if $$$s=\texttt{"andrea"}$$$, you can choose the $$$k=4$$$ characters $$$\texttt{"a_d_ea"}$$$ and permute them into $$$\texttt{"d_e_aa"}$$$ so that after the operation the string becomes $$$\texttt{"dneraa"}$$$.

Determine the minimum $$$k$$$ so that it is possible to sort $$$s$$$ alphabetically (that is, after the operation its characters appear in alphabetical order).

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 40$$$) — the length of the string.

The second line of each test case contains the string $$$s$$$. It is guaranteed that $$$s$$$ contains only lowercase letters of the English alphabet.

Output

For each test case, output the minimum $$$k$$$ that allows you to obtain a string sorted alphabetically, through the operation described above.

Example

Input

4 3 lol 10 codeforces 5 aaaaa 4 dcba

Output

2 6 0 4

Note

In the first test case, we can choose the $$$k=2$$$ characters $$$\texttt{"_ol"}$$$ and rearrange them as $$$\texttt{"_lo"}$$$ (so the resulting string is $$$\texttt{"llo"}$$$). It is not possible to sort the string choosing strictly less than $$$2$$$ characters.

In the second test case, one possible way to sort $$$s$$$ is to consider the $$$k=6$$$ characters $$$\texttt{"_o__force_"}$$$ and rearrange them as $$$\texttt{"_c__efoor_"}$$$ (so the resulting string is $$$\texttt{"ccdeefoors"}$$$). One can show that it is not possible to sort the string choosing strictly less than $$$6$$$ characters.

In the third test case, string $$$s$$$ is already sorted (so we can choose $$$k=0$$$ characters).

In the fourth test case, we can choose all $$$k=4$$$ characters $$$\texttt{"dcba"}$$$ and reverse the whole string (so the resulting string is $$$\texttt{"abcd"}$$$).

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 05:26:40 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|