Little Cyan Fish pitää merkkijonoteoriasta erittäin paljon. Tänään Little Cyan Fish kutsuu sinut jatkamaan ihmisten lempinimien tutkimista hänen kanssaan.
Little Cyan Fishin universumissa ihmisen lempinimi voidaan esittää merkkijonona, joka koostuu vain pienistä latinalaisista kirjaimista (a–z). Esimerkiksi “qingyu” ja “xiuga” ovat ihmisten lempinimiä, mutta “Abacde” ei ole.
Little Cyan Fish pitää nimeä $s$ Lyndon-merkkijonona jos ja vain jos $s$ on leksikografisesti pienempi$^*$ kuin jokainen merkkijonon $s$ aito loppuosa$^\dagger$ $t$. Esimerkiksi “abacde” on Lyndon-merkkijono, mutta “qingyu” ei ole Lyndon-merkkijono (koska se ei ole leksikografisesti pienempi kuin sen aito loppuosa “ingyu”).
Nyt Little Cyan Fish antaa sinulle pituutta $n$ olevan ihmisen lempinimen $s$. Yhdessä operaatiossa voit valita yhden kohdan ja korvata siinä olevan merkin millä tahansa pienellä latinalaisella kirjaimella. Selvitä pienin määrä operaatioita, jotka tarvitaan muuttamaan $s$ Lyndon-merkkijonoksi.
$^*$ Merkkijono on leksikografisesti pienempi kuin toinen merkkijono, jos se on toisen merkkijonon aito alkuosa, tai jos sen merkki ensimmäisessä kohdassa, jossa merkkijonot eroavat toisistaan, on aakkosissa aiempana.
$^\dagger$ Aito loppuosa on epätyhjä loppuosa, joka ei ole sama kuin alkuperäinen merkkijono. Esimerkiksi merkkijonolla “qqoj” on $3$ aitoa loppuosaa, jotka ovat “j”, “oj” ja “qoj”.
Syöte
Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmoittaa testitapausten lukumäärän.
Jokaisessa testitapauksessa ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 3000$). Toinen rivi sisältää pituutta $n$ olevan merkkijonon $s$, joka koostuu vain pienistä latinalaisista kirjaimista.
On taattu, että lukujen $n^2$ summa yli kaikkien testitapausten ei ylitä arvoa $9 \times 10^6$.
Tuloste
Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun: pienimmän määrän operaatioita, jotka tarvitaan muuttamaan $s$ Lyndon-merkkijonoksi.
Esimerkit
Syöte 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
Tuloste 1
0 1 2 3
Huomautus
Ensimmäisessä esimerkkitestitapauksessa merkkijono on jo valmiiksi Lyndon-merkkijono, joten operaatioita ei tarvita.
Toisessa esimerkkitestitapauksessa Little Cyan Fish voi muuttaa viimeisen merkin kirjaimeksi b, jolloin saadaan aaab.
Kolmannessa esimerkkitestitapauksessa hän voi muuttaa ensimmäisen ja viimeisen merkin kirjaimiksi a ja c tässä järjestyksessä, jolloin saadaan abac. Yksi operaatio ei riitä.
Neljännessä esimerkkitestitapauksessa hän voi muuttaa kaksi ensimmäistä merkkiä kirjaimeksi a ja viimeisen merkin kirjaimeksi b, jolloin saadaan aaaab. Tätä on mahdotonta saavuttaa vähemmällä kuin kolmella operaatiolla.