A Little Cyan Fish le gusta mucho la teoría de cadenas. Hoy, Little Cyan Fish te invita a seguir estudiando apodos humanos con él.
En el universo de Little Cyan Fish, un apodo humano se puede representar como una cadena formada únicamente por letras latinas minúsculas (a a z). Por ejemplo, “qingyu” y “xiuga” son apodos humanos, pero “Abacde” no lo es.
Little Cyan Fish considera que un nombre $s$ es una cadena de Lyndon si y solo si $s$ es lexicográficamente menor$^*$ que cada sufijo propio$^\dagger$ $t$ de $s$. Por ejemplo, “abacde” es una cadena de Lyndon, pero “qingyu” no es una cadena de Lyndon (porque no es lexicográficamente menor que su sufijo propio “ingyu”).
Ahora, Little Cyan Fish te da un apodo humano $s$ de longitud $n$. En una operación, puedes elegir una posición y reemplazar su carácter por cualquier letra latina minúscula. Encuentra el número mínimo de operaciones necesarias para convertir $s$ en una cadena de Lyndon.
$^*$ Una cadena es lexicográficamente menor que otra cadena si es un prefijo propio de la otra cadena, o si su carácter en la primera posición donde las cadenas difieren aparece antes en el alfabeto.
$^\dagger$ Un sufijo propio es un sufijo no vacío que no es igual a la cadena original. Por ejemplo, “qqoj” tiene $3$ sufijos propios, que son “j”, “oj” y “qoj”.
Entrada
Hay múltiples casos de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T \le 10^4$), que indica el número de casos de prueba.
Para cada caso de prueba, la primera línea contiene un solo entero $n$ ($1 \le n \le 3000$). La segunda línea contiene una cadena $s$ de longitud $n$, formada únicamente por letras latinas minúsculas.
Se garantiza que la suma de $n^2$ en todos los casos de prueba no supera $9 \times 10^6$.
Salida
Para cada caso de prueba, imprime una sola línea con un solo entero, que indique el número mínimo de operaciones necesarias para convertir $s$ en una cadena de Lyndon.
Ejemplos
Entrada 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
Salida 1
0 1 2 3
Nota
En el primer caso de prueba de ejemplo, la cadena ya es una cadena de Lyndon, por lo que no se necesita ninguna operación.
En el segundo caso de prueba de ejemplo, Little Cyan Fish puede cambiar el último carácter a b, obteniendo aaab.
En el tercer caso de prueba de ejemplo, puede cambiar el primer y el último carácter a a y c, respectivamente, obteniendo abac. Una sola operación no es suficiente.
En el cuarto caso de prueba de ejemplo, puede cambiar los dos primeros caracteres a a y el último carácter a b, obteniendo aaaab. Es imposible lograr esto en menos de tres operaciones.