小青鱼非常喜欢字符串理论。今天，小青鱼邀请你继续和他一起研究人类的昵称。

在小青鱼的宇宙中，一个人类昵称可以表示为一个仅由小写拉丁字母（a 到 z）组成的字符串。例如，“qingyu”和“xiuga”是人类昵称，但“Abacde”不是。

小青鱼认为一个名字 $s$ 是 Lyndon 串，当且仅当 $s$ 的字典序小于$^*$ $s$ 的每一个真后缀$^\dagger$ $t$。例如，“abacde”是 Lyndon 串，但“qingyu”不是 Lyndon 串（因为它的字典序并不小于它的真后缀“ingyu”）。

现在，小青鱼给你一个长度为 $n$ 的人类昵称 $s$。在一次操作中，你可以选择一个位置，并将其上的字符替换为任意小写拉丁字母。请你求出将 $s$ 变为 Lyndon 串所需的最少操作次数。

$^*$ 如果一个字符串是另一个字符串的真前缀，或者在两个字符串第一个不同的位置上，该字符串的字符在字母表中出现得更早，则称该字符串的字典序小于另一个字符串。

$^\dagger$ 真后缀是指不等于原字符串的非空后缀。例如，“qqoj”有 $3$ 个真后缀，分别为“j”、“oj”和“qoj”。

输入格式

本题包含多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$（$1 \le n \le 3000$）。第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写拉丁字母组成。

保证所有测试数据中 $n^2$ 的总和不超过 $9 \times 10^6$。

输出格式

对于每组测试数据，输出一行一个整数，表示将 $s$ 变为 Lyndon 串所需的最少操作次数。

样例

输入格式 1

4
4
abac
4
aaaa
4
bbaa
5
bbaaa

输出格式 1

0
1
2
3

说明

在第一组样例测试数据中，该字符串已经是 Lyndon 串，因此不需要任何操作。

在第二组样例测试数据中，小青鱼可以将最后一个字符修改为 b，得到 aaab。

在第三组样例测试数据中，他可以将第一个字符和最后一个字符分别修改为 a 和 c，得到 abac。仅进行一次操作是不够的。

在第四组样例测试数据中，他可以将前两个字符修改为 a，并将最后一个字符修改为 b，得到 aaaab。无法用少于三次操作达成目标。