Little Cyan Fish очень любит теорию строк. Сегодня Little Cyan Fish приглашает вас продолжить вместе с ним изучение человеческих никнеймов.
Во вселенной Little Cyan Fish человеческий никнейм можно представить в виде строки, состоящей только из строчных латинских букв (от a до z). Например, «qingyu» и «xiuga» являются человеческими никнеймами, а «Abacde» — нет.
Little Cyan Fish считает имя $s$ строкой Линдона тогда и только тогда, когда $s$ лексикографически меньше$^*$ каждого собственного суффикса$^\dagger$ $t$ строки $s$. Например, «abacde» является строкой Линдона, а «qingyu» не является строкой Линдона (поскольку она не лексикографически меньше своего собственного суффикса «ingyu»).
Теперь Little Cyan Fish даёт вам человеческий никнейм $s$ длины $n$. За одну операцию вы можете выбрать одну позицию и заменить символ в ней на любую строчную латинскую букву. Найдите минимальное количество операций, необходимое для того, чтобы сделать $s$ строкой Линдона.
$^*$ Строка лексикографически меньше другой строки, если она является собственным префиксом другой строки или если её символ в первой позиции, где строки различаются, идёт раньше в алфавите.
$^\dagger$ Собственный суффикс — это непустой суффикс, не равный исходной строке. Например, у строки «qqoj» есть $3$ собственных суффикса: «j», «oj» и «qoj».
Входные данные
Входные данные состоят из нескольких наборов входных данных. Первая строка входных данных содержит одно целое число $T$ ($1 \le T \le 10^4$), обозначающее количество наборов входных данных.
Для каждого набора входных данных первая строка содержит одно целое число $n$ ($1 \le n \le 3000$). Вторая строка содержит строку $s$ длины $n$, состоящую только из строчных латинских букв.
Гарантируется, что сумма $n^2$ по всем наборам входных данных не превышает $9 \times 10^6$.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую одно целое число — минимальное количество операций, необходимое для того, чтобы сделать $s$ строкой Линдона.
Примеры
Входные данные 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
Выходные данные 1
0 1 2 3
Примечание
В первом тестовом примере строка уже является строкой Линдона, поэтому никаких операций не требуется.
Во втором тестовом примере Little Cyan Fish может изменить последний символ на b, получив aaab.
В третьем тестовом примере он может изменить первый и последний символы на a и c соответственно, получив abac. Одной операции недостаточно.
В четвёртом тестовом примере он может изменить первые два символа на a, а последний символ — на b, получив aaaab. Добиться этого менее чем за три операции невозможно.