给出一个长度为 $$$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$$$ 进行排序(即,在操作之后,其字符按字母顺序出现)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 40$$$) — 字符串的长度。
每个测试用例的第二行包含字符串$$$s$$$。保证 $$$s$$$ 仅包含英文字母表中的小写字母。
输出
对于每个测试用例,通过上述操作,输出允许您获得按字母顺序排序的字符串的最小$$$k$$$。
示例
输入 #1
4 3 lol 10 codeforces 5 aaaaa 4 dcba
输出 #1
2 6 0 4
注意
在第一个测试用例中,我们可以选择 $$$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"}$$$)。