Little Cyan Fish heldur mjög mikið upp á strengjafræði. Í dag býður Little Cyan Fish þér að halda áfram að rannsaka gælunöfn manna með sér.

Í alheimi Little Cyan Fish er hægt að tákna gælunafn manns sem streng sem samanstendur eingöngu af latneskum lágstöfum (a til z). Til dæmis eru “qingyu” og “xiuga” gælunöfn manna, en “Abacde” er það ekki.

Little Cyan Fish telur nafn $s$ vera Lyndon-streng ef og aðeins ef $s$ er í stafrófsröð minni$^*$ en sérhver eiginleg ending$^\dagger$ $t$ í $s$. Til dæmis er “abacde” Lyndon-strengur, en “qingyu” er ekki Lyndon-strengur (því hann er ekki í stafrófsröð minni en eiginleg ending hans “ingyu”).

Nú gefur Little Cyan Fish þér gælunafn manns $s$ af lengd $n$. Í einni aðgerð geturðu valið einn stað og skipt stafnum þar út fyrir hvaða latneska lágstaf sem er. Finndu lágmarksfjölda aðgerða sem þarf til að gera $s$ að Lyndon-streng.

$^*$ Strengur er í stafrófsröð minni en annar strengur ef hann er eiginlegt forskeyti hins strengsins, eða ef stafur hans á fyrsta staðnum þar sem strengirnir eru ólíkir kemur fyrr í stafrófinu.

$^\dagger$ Eiginleg ending er ótóm ending sem er ekki jöfn upphaflega strengnum. Til dæmis hefur “qqoj” $3$ eiginlegar endingar, sem eru “j”, “oj” og “qoj”.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 10^4$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan eina heiltölu $n$ ($1 \le n \le 3000$). Önnur línan inniheldur streng $s$ af lengd $n$, sem samanstendur eingöngu af latneskum lágstöfum.

Það er tryggt að summan af $n^2$ yfir öll prófunartilvik fari ekki yfir $9 \times 10^6$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu, sem gefur til kynna lágmarksfjölda aðgerða sem þarf til að gera $s$ að Lyndon-streng.

Dæmi

Inntak 1

4
4
abac
4
aaaa
4
bbaa
5
bbaaa

Úttak 1

0
1
2
3

Athugasemd

Í fyrsta sýnidæminu er strengurinn þegar Lyndon-strengur, svo engin aðgerð er nauðsynleg.

Í öðru sýnidæminu getur Little Cyan Fish breytt síðasta stafnum í b og fengið aaab.

Í þriðja sýnidæminu getur hann breytt fyrsta og síðasta stafnum í a og c, í þessari röð, og fengið abac. Ein aðgerð dugar ekki.

Í fjórða sýnidæminu getur hann breytt fyrstu tveimur stöfunum í a og síðasta stafnum í b og fengið aaaab. Það er ómögulegt að ná þessu í færri en þremur aðgerðum.