Little Cyan Fish liker strengteori svært godt. I dag inviterer Little Cyan Fish deg til å studere menneskelige kallenavn sammen med ham.

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

Little Cyan Fish regner et navn $s$ som Lyndon hvis og bare hvis den leksikografiske rekkefølgen til $s$ er strengt mindre enn $t$ for hvert ekte suffiks* $t$ av $s$. For eksempel er "abacde" en Lyndon-streng, men "qingyu" er ikke en Lyndon-streng (fordi den opprinnelige strengen ikke er leksikografisk mindre enn det ekte suffikset "ingyu").

Nå gir Little Cyan Fish deg et menneskelig kallenavn $s$, og du må beregne hvor mange forskjellige par $(l, r)$ med $1 \le l \le r \le |s|$ som finnes slik at $s[l \dots r]$ er Lyndon.

* 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 av inndataene inneholder et enkelt heltall $T$ ($1 \le T$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder inndataene én enkelt linje med en streng $s$ ($1 \le |s| \le 2 \times 10^5$), som angir det menneskelige kallenavnet.

Det er garantert at summen av $|s|$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder ett heltall, som angir svaret.

Eksempel

Inndata 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Utdata 1

3
9
27
16
58
32