Little Cyan Fish tycker väldigt mycket om strängteori. Idag bjuder Little Cyan Fish in dig att fortsätta studera mänskliga smeknamn tillsammans med honom.

I Little Cyan Fishs universum kan ett mänskligt smeknamn representeras som en sträng som endast består av små latinska bokstäver (a till z). Till exempel är “qingyu” och “xiuga” mänskliga smeknamn, men “Abacde” är det inte.

Little Cyan Fish anser att ett namn $s$ är en Lyndonsträng om och endast om $s$ är lexikografiskt mindre$^*$ än varje äkta suffix$^\dagger$ $t$ av $s$. Till exempel är “abacde” en Lyndonsträng, men “qingyu” är inte en Lyndonsträng (eftersom den inte är lexikografiskt mindre än sitt äkta suffix “ingyu”).

Nu ger Little Cyan Fish dig ett mänskligt smeknamn $s$ av längd $n$. I en operation kan du välja en position och ersätta dess tecken med valfri liten latinsk bokstav. Hitta det minsta antalet operationer som krävs för att göra $s$ till en Lyndonsträng.

$^*$ En sträng är lexikografiskt mindre än en annan sträng om den är ett äkta prefix av den andra strängen, eller om dess tecken på den första positionen där strängarna skiljer sig åt kommer tidigare i alfabetet.

$^\dagger$ Ett äkta suffix är ett icke-tomt suffix som inte är lika med den ursprungliga strängen. Till exempel har “qqoj” $3$ äkta suffix, vilka är “j”, “oj” och “qoj”.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T \le 10^4$), som anger antalet testfall.

För varje testfall innehåller den första raden ett enda heltal $n$ ($1 \le n \le 3000$). Den andra raden innehåller en sträng $s$ av längd $n$, som endast består av små latinska bokstäver.

Det garanteras att summan av $n^2$ över alla testfall inte överstiger $9 \times 10^6$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett enda heltal, vilket anger det minsta antalet operationer som krävs för att göra $s$ till en Lyndonsträng.

Exempel

Indata 1

4
4
abac
4
aaaa
4
bbaa
5
bbaaa

Utdata 1

0
1
2
3

Förklaring

I det första exempeltestfallet är strängen redan en Lyndonsträng, så ingen operation behövs.

I det andra exempeltestfallet kan Little Cyan Fish ändra det sista tecknet till b och få aaab.

I det tredje exempeltestfallet kan han ändra det första och det sista tecknet till a respektive c, och få abac. En operation räcker inte.

I det fjärde exempeltestfallet kan han ändra de två första tecknen till a och det sista tecknet till b, och få aaaab. Det är omöjligt att uppnå detta med färre än tre operationer.