Little Cyan Fish bardzo lubi teorię tekstów. Dzisiaj Little Cyan Fish zaprasza cię do wspólnego badania ludzkich pseudonimów.

We wszechświecie Little Cyan Fisha wszystkie ludzkie pseudonimy można przedstawić jako napisy zawierające wyłącznie małe litery alfabetu łacińskiego (od a do z). Na przykład "qingyu" i "xiuga" są ludzkimi pseudonimami, ale "Abacde" nie jest ludzkim pseudonimem.

Little Cyan Fish uważa imię $s$ za słowo Lyndona wtedy i tylko wtedy, gdy dla każdego właściwego sufiksu* $t$ napisu $s$, napis $s$ jest leksykograficznie ostro mniejszy od $t$. Na przykład "abacde" jest słowem Lyndona, ale "qingyu" nie jest słowem Lyndona (ponieważ oryginalny napis nie jest mniejszy leksykograficznie od właściwego sufiksu "ingyu").

Teraz Little Cyan Fish daje ci ludzki pseudonim $s$, a twoim zadaniem jest obliczenie, ile istnieje różnych par $(l, r)$ spełniających $1 \le l \le r \le |s|$, takich że $s[l \dots r]$ jest słowem Lyndona.

* Właściwy sufiks to niepusty sufiks, który nie jest równy oryginalnemu napisowi. Na przykład "qqoj" ma $3$ właściwe sufiksy: "j", "oj" oraz "qoj".

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego wejście zawiera pojedynczy wiersz z napisem $s$ ($1 \le |s| \le 2 \times 10^5$), oznaczającym ludzki pseudonim.

Gwarantowane jest, że suma $|s|$ po wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz pojedynczy wiersz zawierający jedną liczbę całkowitą, oznaczającą odpowiedź.

Przykład

Wejście 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Wyjście 1

3
9
27
16
58
32