310888: CF1905C. Largest Subsequence

C. Largest Subsequencetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Given is a string $s$ of length $n$. In one operation you can select the lexicographically largest$^\dagger$ subsequence of string $s$ and cyclic shift it to the right$^\ddagger$.

Your task is to calculate the minimum number of operations it would take for $s$ to become sorted, or report that it never reaches a sorted state.

$^\dagger$A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$;
• In the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

$^\ddagger$By cyclic shifting the string $t_1t_2\ldots t_m$ to the right, we get the string $t_mt_1\ldots t_{m-1}$.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line of each test case contains a single string $s$ of length $n$, consisting of lowercase English letters.

It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of operations required to make $s$ sorted, or $-1$ if it's impossible.

ExampleInput

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

Output

0
1
-1
2
6
0

Note

In the first test case, the string $s$ is already sorted, so we need no operations.

In the second test case, doing one operation, we will select cb and cyclic shift it. The string $s$ is now abc which is sorted.

In the third test case, $s$ cannot be sorted.

In the fourth test case we will perform the following operations:

• The lexicographically largest subsequence is zca. Then $s$ becomes abzc.
• The lexicographically largest subsequence is zc. Then $s$ becomes abcz. The string becomes sorted.

Thus, we need $2$ operations.

题目大意：
给定一个长度为n的字符串s。每次操作可以选择字符串s的字典序最大的子序列，并将其循环右移。任务是计算使s变得有序所需的最小操作次数，或者报告s永远无法达到有序状态。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——字符串s的长度。
每个测试用例的第二行包含一个长度为n的字符串s，由小写英文字母组成。
保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一个整数——使s有序所需的最小操作次数，或者如果不可能，则输出-1。

示例：
输入
```
6
5
aaabc
3
acb
3
bac
4
zbca
15
czddeneeeemigec
13
cdefmopqsvxzz
```
输出
```
0
1
-1
2
6
0
```

注意：
- 在第一个测试用例中，字符串s已经有序，所以不需要操作。
- 在第二个测试用例中，进行一次操作，选择"cb"并循环右移。字符串s现在是"abc"，它是有序的。
- 在第三个测试用例中，s无法变得有序。
- 在第四个测试用例中，执行以下操作：
- 字典序最大的子序列是"zca"。然后s变成"abzc"。
- 字典序最大的子序列是"zc"。然后s变成"abcz"。字符串变得有序。
因此，我们需要2次操作。题目大意： 给定一个长度为n的字符串s。每次操作可以选择字符串s的字典序最大的子序列，并将其循环右移。任务是计算使s变得有序所需的最小操作次数，或者报告s永远无法达到有序状态。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——字符串s的长度。 每个测试用例的第二行包含一个长度为n的字符串s，由小写英文字母组成。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数——使s有序所需的最小操作次数，或者如果不可能，则输出-1。 示例： 输入 ``` 6 5 aaabc 3 acb 3 bac 4 zbca 15 czddeneeeemigec 13 cdefmopqsvxzz ``` 输出 ``` 0 1 -1 2 6 0 ``` 注意： - 在第一个测试用例中，字符串s已经有序，所以不需要操作。 - 在第二个测试用例中，进行一次操作，选择"cb"并循环右移。字符串s现在是"abc"，它是有序的。 - 在第三个测试用例中，s无法变得有序。 - 在第四个测试用例中，执行以下操作： - 字典序最大的子序列是"zca"。然后s变成"abzc"。 - 字典序最大的子序列是"zc"。然后s变成"abcz"。字符串变得有序。 因此，我们需要2次操作。