Little Cyan Fish pitää merkkijonoteoriasta erittäin paljon. Tänään Little Cyan Fish kutsuu sinut tutkimaan ihmisten lempinimiä kanssaan.

Little Cyan Fishin universumissa kaikki ihmisten lempinimet voidaan esittää merkkijonoina, jotka sisältävät vain pieniä latinalaisia kirjaimia (a–z). Esimerkiksi "qingyu" ja "xiuga" ovat ihmisten lempinimiä, mutta "Abacde" ei ole ihmisen lempinimi.

Little Cyan Fish pitää nimeä $s$ Lyndon-merkkijonona, jos ja vain jos jokaiselle merkkijonon $s$ aidolle loppuosalle* $t$ merkkijono $s$ on aakkosjärjestyksessä (leksikografisesti) aidosti pienempi kuin $t$. Esimerkiksi "abacde" on Lyndon-merkkijono, mutta "qingyu" ei ole Lyndon-merkkijono (koska alkuperäinen merkkijono ei ole leksikografisesti pienempi kuin aito loppuosa "ingyu").

Nyt Little Cyan Fish antaa sinulle ihmisen lempinimen $s$, ja sinun tulee laskea, kuinka monta eri paria $(l, r)$ väliltä $1 \le l \le r \le |s|$ on olemassa niin, että $s[l \dots r]$ on Lyndon.

* Aito loppuosa (proper suffix) on epätyhjä loppuosa, joka ei ole yhtä suuri 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$), joka ilmoittaa testitapausten lukumäärän.

Jokaisessa testitapauksessa syöte sisältää yhden rivin, jolla on ihmisen lempinimeä kuvaava merkkijono $s$ ($1 \le |s| \le 2 \times 10^5$).

On taattua, että pituuksien $|s|$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun — vastauksen.

Esimerkki

Syöte 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Tuloste 1

3
9
27
16
58
32