Little Cyan Fish tycker mycket om strängteori. Idag bjuder Little Cyan Fish in dig att studera mänskliga smeknamn tillsammans med honom.

I Little Cyan Fishs universum kan alla mänskliga smeknamn representeras som en sträng som endast innehåller små latinska bokstäver (a till z). Till exempel är "qingyu" och "xiuga" mänskliga smeknamn, men "Abacde" är inte ett mänskligt smeknamn.

Little Cyan Fish anser att ett namn $s$ är Lyndon om och endast om den lexikografiska ordningen för $s$ är strikt mindre än $t$ för varje äkta suffix* $t$ till $s$. Till exempel är "abacde" en Lyndonsträng, men "qingyu" är inte en Lyndonsträng (eftersom den ursprungliga strängen inte är lexikografiskt mindre än det äkta suffixet "ingyu").

Nu ger Little Cyan Fish dig ett mänskligt smeknamn $s$, och du ska beräkna hur många olika par $(l, r)$ med $1 \le l \le r \le |s|$ som existerar sådana att $s[l \dots r]$ är Lyndon.

* Ett äkta suffix är ett icke-tomt suffix som inte är lika med den ursprungliga strängen. Till exempel har "qqoj" $3$ äkta suffix, vilka är "j", "oj" och "qoj".

Indata

Det finns flera testfall. Den första raden i indata innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller indata en enda rad med en sträng $s$ ($1 \le |s| \le 2 \times 10^5$), som anger det mänskliga smeknamnet.

Det garanteras att summan av $|s|$ över alla testfall inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett heltal som anger svaret.

Exempel

Indata 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Utdata 1

3
9
27
16
58
32