CF1552A.Subsequence Permutation

A 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).

给定一个长度为 $n$ 的字符串 $s$，它仅由小写英文字母组成。

你需要选择一个介于 $0$ 和 $n$ 之间的整数 $k$。然后，从 $s$ 中选出 $k$ 个字符，并以任意方式对其重排（即置换）。在此过程中，其余 $n-k$ 个字符的位置保持不变。你必须恰好执行一次该操作。

例如，若 $s=\texttt{"andrea"}$，你可以选择 $k=4$ 个字符 \texttt{"a_d_ea"}（下划线表示保留原位置的其他字符），并将它们重排为 \texttt{"d_e_aa"}，使得操作后字符串变为 $\texttt{"dneraa"}$。

请确定最小的 $k$，使得通过上述操作能够将 $s$ 按字母序排序（即操作后其字符按字典序非降序排列）。

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.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 40$）—— 表示字符串的长度。

每个测试用例的第二行包含字符串 $s$。保证 $s$ 仅由英文字母的小写字母组成。

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

对于每个测试用例，输出能够通过上述操作得到按字母顺序排序的字符串的最小 $k$ 值。

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"}$).

在第一个测试用例中，我们可以选择 $k=2$ 个字符 \texttt{"_ol"}，并将它们重排为 \texttt{"_lo"}（因此得到的字符串为 $\texttt{"llo"}$）。无法通过选择严格少于 $2$ 个字符来将该字符串排序。

在第二个测试用例中，一种将 $s$ 排序的可行方法是：选择 $k=6$ 个字符 \texttt{"_o__force_"}，并将它们重排为 \texttt{"_c__efoor_"}（因此得到的字符串为 $\texttt{"ccdeefoors"}$）。可以证明，无法通过选择严格少于 $6$ 个字符来将该字符串排序。

在第三个测试用例中，字符串 $s$ 已经是有序的（因此我们可以选择 $k=0$ 个字符）。

在第四个测试用例中，我们可以选择全部 $k=4$ 个字符 $\texttt{"dcba"}$，并反转整个字符串（因此得到的字符串为 $\texttt{"abcd"}$）。