C. 最大子序列

每个测试点时间限制： $1$ 秒

每个测试点内存限制： $256$ 兆字节

给定一个长度为 $n$ 的字符串 $s$ 。

一次操作中，你可以选择字符串 $s$ 的字典序最大子序列，并将这个子序列进行一次循环右移。

你的任务是计算：最少需要多少次操作，才能使字符串 $s$ 变为有序；如果永远无法变为有序，则输出 $-1$ 。

其中：

若字符串 $a$ $a$ 与字符串 $b$ $b$ 满足以下任意一种情况，则称 $a$ $a$ 的字典序小于 $b$ $b$ ：
- $a$ 是 $b$ 的前缀，但 $a \ne b$ ；
- 在两者第一次不同的位置上，字符串 $a$ 的该位置字符在字母表中早于字符串 $b$ 对应位置的字符。
对字符串 $t_1 t_2 \dots t_m$ 进行一次循环右移后，会变为：

t_m t_1 \dots t_{m-1}

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$ ，表示测试数据组数，其中：

1 \le t \le 10^4

对于每组测试数据：

第一行包含一个整数 $n$ ，表示字符串 $s$ 的长度，其中：

1 \le n \le 2 \cdot 10^5

第二行包含一个长度为 $n$ 的字符串 $s$ ，仅由小写英文字母组成。

保证所有测试数据中 $n$ 的总和不超过：

2 \cdot 10^5

对于每组测试数据，输出一个整数，表示让字符串 $s$ 变为有序所需的最少操作次数；如果无法做到，则输出 $-1$ 。

6
5
aaabc
3
acb
3
bac
4
zbca
15
czddeneeeemigec
13
cdefmopqsvxzz

在第 $1$ 组测试数据中，字符串 $s$ 已经有序，因此不需要任何操作。

在第 $2$ 组测试数据中，进行一次操作后，我们会选择子序列 $cb$ 并将其循环右移。此时字符串 $s$ 变为 $abc$ ，已经有序。

在第 $3$ 组测试数据中，字符串 $s$ 无法变为有序。

在第 $4$ 组测试数据中，操作过程如下：

此时字符串已经有序，因此答案是 $2$ 。