Little Cyan Fish hefur mjög gaman af strengjafræði. Í dag býður Little Cyan Fish þér að rannsaka gælunöfn manna með sér.

Í alheimi Little Cyan Fish er hægt að tákna öll gælunöfn manna sem streng sem inniheldur eingöngu latneska lágstafi (a til z). Til dæmis eru "qingyu" og "xiuga" gælunöfn manna, en "Abacde" er ekki gælunafn manns.

Little Cyan Fish telur nafn $s$ vera Lyndon ef og aðeins ef fyrir sérhvern eiginlegan endingarhluta* $t$ af $s$ er stafrófsröð $s$ strangt minni en $t$. Til dæmis er "abacde" Lyndon-strengur, en "qingyu" er ekki Lyndon-strengur (því upphaflegi strengurinn er ekki minni í stafrófsröð en eiginlegi endingarhlutinn "ingyu").

Nú gefur Little Cyan Fish þér gælunafn manns $s$, og þú þarft að reikna hversu mörg ólík pör $(l, r)$ með $1 \le l \le r \le |s|$ eru til þannig að $s[l \dots r]$ sé Lyndon.

* Eiginlegur endingarhluti (proper suffix) er ótómur endingarhluti sem er ekki jafn upphaflega strengnum. Til dæmis hefur "qqoj" $3$ eiginlega endingarhluta, 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$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur inntakið eina línu með streng $s$ ($1 \le |s| \le 2 \times 10^5$), sem gefur til kynna gælunafn mannsins.

Tryggt er að summa $|s|$ yfir öll prófunartilvik fer ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu, sem gefur til kynna svarið.

Dæmi

Inntak 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Úttak 1

3
9
27
16
58
32