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$ рядком Ліндона.

Приклади

Input 1

4
4
abac
4
aaaa
4
bbaa
5
bbaaa

Output 1

0
1
2
3

Note

У першому тестовому прикладі рядок уже є рядком Ліндона, тому жодних операцій не потрібно.

У другому тестовому прикладі Little Cyan Fish може змінити останній символ на b, отримавши aaab.

У третьому тестовому прикладі він може змінити перший і останній символи на a та c відповідно, отримавши abac. Однієї операції недостатньо.

У четвертому тестовому прикладі він може змінити перші два символи на a, а останній символ — на b, отримавши aaaab. Досягти цього менш ніж за три операції неможливо.