C. Наибольшая подпоследовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$ длины $$$n$$$. За одну операцию можно выбрать лексикографически наибольшую$$$^\dagger$$$ подпоследовательность строки $$$s$$$ и циклически сдвинуть её вправо$$$^\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$$$.

Вторая строка каждого набора входных данных содержит одну строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 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$$$ операции.