A. Subsequence Permutation
sortings; strings
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).
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.
For each test case, output the minimum \(k\) that allows you to obtain a string sorted alphabetically, through the operation described above.
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""}\)).