Little Cyan Fish aime beaucoup la théorie des chaînes de caractères. Aujourd'hui, Little Cyan Fish vous invite à continuer d'étudier les surnoms humains avec lui.
Dans l'univers de Little Cyan Fish, un surnom humain peut être représenté par une chaîne composée uniquement de lettres latines minuscules (a à z). Par exemple, « qingyu » et « xiuga » sont des surnoms humains, mais « Abacde » ne l'est pas.
Little Cyan Fish considère qu'un nom $s$ est un mot de Lyndon si et seulement si $s$ est lexicographiquement plus petit$^*$ que chaque suffixe propre$^\dagger$ $t$ de $s$. Par exemple, « abacde » est un mot de Lyndon, mais « qingyu » n'est pas un mot de Lyndon (car il n'est pas lexicographiquement plus petit que son suffixe propre « ingyu »).
Maintenant, Little Cyan Fish vous donne un surnom humain $s$ de longueur $n$. En une opération, vous pouvez choisir une position et remplacer son caractère par n'importe quelle lettre latine minuscule. Trouvez le nombre minimum d'opérations nécessaires pour transformer $s$ en un mot de Lyndon.
$^*$ Une chaîne est lexicographiquement plus petite qu'une autre chaîne si elle est un préfixe propre de l'autre chaîne, ou si son caractère à la première position où les chaînes diffèrent apparaît plus tôt dans l'alphabet.
$^\dagger$ Un suffixe propre est un suffixe non vide qui n'est pas égal à la chaîne d'origine. Par exemple, « qqoj » possède $3$ suffixes propres, qui sont « j », « oj » et « qoj ».
Entrée
Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T \le 10^4$), indiquant le nombre de cas de test.
Pour chaque cas de test, la première ligne contient un seul entier $n$ ($1 \le n \le 3000$). La deuxième ligne contient une chaîne $s$ de longueur $n$, composée uniquement de lettres latines minuscules.
Il est garanti que la somme de $n^2$ sur tous les cas de test ne dépasse pas $9 \times 10^6$.
Sortie
Pour chaque cas de test, affichez une seule ligne contenant un seul entier, indiquant le nombre minimum d'opérations nécessaires pour transformer $s$ en un mot de Lyndon.
Exemples
Entrée 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
Sortie 1
0 1 2 3
Remarque
Dans le premier cas de test de l'exemple, la chaîne est déjà un mot de Lyndon, donc aucune opération n'est nécessaire.
Dans le deuxième cas de test de l'exemple, Little Cyan Fish peut remplacer le dernier caractère par b, obtenant ainsi aaab.
Dans le troisième cas de test de l'exemple, il peut remplacer le premier et le dernier caractère par a et c, respectivement, obtenant ainsi abac. Une seule opération ne suffit pas.
Dans le quatrième cas de test de l'exemple, il peut remplacer les deux premiers caractères par a et le dernier caractère par b, obtenant ainsi aaaab. Il est impossible d'y parvenir en moins de trois opérations.