Little Cyan Fish liker strengteori veldig godt. I dag inviterer Little Cyan Fish deg til å fortsette å studere menneskelige kallenavn sammen med ham.

I Little Cyan Fish sitt univers kan et menneskelig kallenavn representeres som en streng som kun består av små latinske bokstaver (a til z). For eksempel er “qingyu” og “xiuga” menneskelige kallenavn, men “Abacde” er det ikke.

Little Cyan Fish anser et navn $s$ for å være en Lyndon-streng hvis og bare hvis $s$ er leksikografisk mindre$^*$ enn hvert ekte suffiks$^\dagger$ $t$ av $s$. For eksempel er “abacde” en Lyndon-streng, men “qingyu” er ikke en Lyndon-streng (fordi den ikke er leksikografisk mindre enn sitt ekte suffiks “ingyu”).

Nå gir Little Cyan Fish deg et menneskelig kallenavn $s$ med lengde $n$. I én operasjon kan du velge én posisjon og erstatte tegnet der med en hvilken som helst liten latinsk bokstav. Finn det minste antallet operasjoner som trengs for å gjøre $s$ til en Lyndon-streng.

$^*$ En streng er leksikografisk mindre enn en annen streng hvis den er et ekte prefiks av den andre strengen, eller hvis tegnet på den første posisjonen der strengene er forskjellige, kommer tidligere i alfabetet.

$^\dagger$ Et ekte suffiks er et ikke-tomt suffiks som ikke er lik den opprinnelige strengen. For eksempel har “qqoj” $3$ ekte suffikser, som er “j”, “oj” og “qoj”.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et enkelt heltall $T$ ($1 \le T \le 10^4$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen et enkelt heltall $n$ ($1 \le n \le 3000$). Den andre linjen inneholder en streng $s$ med lengde $n$, som kun består av små latinske bokstaver.

Det er garantert at summen av $n^2$ over alle testtilfeller ikke overstiger $9 \times 10^6$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder et enkelt heltall, som angir det minste antallet operasjoner som trengs for å gjøre $s$ til en Lyndon-streng.

Eksempler

Inndata 1

4
4
abac
4
aaaa
4
bbaa
5
bbaaa

Utdata 1

0
1
2
3

Merk

I det første eksempeltesttilfellet er strengen allerede en Lyndon-streng, så ingen operasjon er nødvendig.

I det andre eksempeltesttilfellet kan Little Cyan Fish endre det siste tegnet til b og få aaab.

I det tredje eksempeltesttilfellet kan han endre det første og det siste tegnet til henholdsvis a og c, og få abac. Én operasjon er ikke nok.

I det fjerde eksempeltesttilfellet kan han endre de to første tegnene til a og det siste tegnet til b, og få aaaab. Det er umulig å oppnå dette med færre enn tre operasjoner.