Subsequence Permutation

题意翻译

### 题目大意： 有 t 组数据，每组数据会给你一个长度为 n 的字符串 s 。 你可以选择 k 个数，并把这 k 个数排序。使字符串 s 最后按照字典序排序。输出 k 的最小值。

题目描述

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.

输入输出样例

输入样例 #1

4
3
lol
10
codeforces
5
aaaaa
4
dcba

输出样例 #1

2
6
0
4

说明

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