给定一个长度为 $$$n$$$ 的字符串 $$$s$$$。在一项操作中,您可以选择字符串 $$$s$$$ 的字典顺序最大的$$$^\dagger$$$ 子序列,并将其循环移位到右侧$$$^\ddagger$$$。
您的任务是计算 $$$s$$$ 排序所需的最少操作数,或者报告它永远不会达到排序状态。
$$$^\dagger$$$当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的对应字母更早出现。
$$$^\ddagger$$$通过将字符串 $$$t_1t_2\ldots t_m$$$ 向右循环移位,我们得到字符串 $$$t_mt_1\ldots t_{m-1}$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由小写英文字母组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 使 $$$s$$$ 排序所需的最少操作数,如果不可能,则输出 $$$-1$$$。
示例
输入 #1
6 5 aaabc 3 acb 3 bac 4 zbca 15 czddeneeeemigec 13 cdefmopqsvxzz
输出 #1
0 1 -1 2 6 0
注意
在第一个测试用例中,字符串 $$$s$$$ 已经排序,因此我们不需要任何操作。
在第二个测试用例中,执行一项操作,我们将选择 cb 并对其进行循环移位。字符串 $$$s$$$ 现在是已排序的 abc。
在第三个测试用例中,$$$s$$$ 无法排序。
在第四个测试用例中我们将执行以下操作:
- 字典顺序最大的子序列是 zca。那么 $$$s$$$ 就变成了 abzc。
- 字典顺序最大的子序列是 zc。那么 $$$s$$$ 就变成了 abcz。字符串已排序。
因此,我们需要 $$$2$$$ 操作。