Little Cyan Fish mag die Theorie der Zeichenketten sehr. Heute lädt Little Cyan Fish dich ein, gemeinsam mit ihm menschliche Spitznamen zu untersuchen.

Im Universum von Little Cyan Fish lassen sich alle menschlichen Spitznamen als Zeichenkette darstellen, die ausschließlich aus lateinischen Kleinbuchstaben (a bis z) besteht. Zum Beispiel sind "qingyu" und "xiuga" menschliche Spitznamen, "Abacde" jedoch nicht.

Little Cyan Fish betrachtet einen Namen $s$ genau dann als Lyndon, wenn für jedes echte Suffix* $t$ von $s$ die Zeichenkette $s$ lexikographisch echt kleiner als $t$ ist. Zum Beispiel ist "abacde" eine Lyndon-Zeichenkette, "qingyu" jedoch nicht (da die ursprüngliche Zeichenkette lexikographisch nicht kleiner als das echte Suffix "ingyu" ist).

Nun gibt Little Cyan Fish dir einen menschlichen Spitznamen $s$, und du musst berechnen, wie viele verschiedene Paare $(l, r)$ mit $1 \le l \le r \le |s|$ existieren, sodass $s[l \dots r]$ Lyndon ist.

* Ein echtes Suffix ist ein nichtleeres Suffix, das nicht gleich der ursprünglichen Zeichenkette ist. Zum Beispiel hat "qqoj" genau $3$ echte Suffixe, nämlich "j", "oj" und "qoj".

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die Eingabe eine einzelne Zeile mit einer Zeichenkette $s$ ($1 \le |s| \le 2 \times 10^5$), die den menschlichen Spitznamen angibt.

Es wird garantiert, dass die Summe von $|s|$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer ganzen Zahl aus, die die Antwort angibt.

Beispiel

Eingabe 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Ausgabe 1

3
9
27
16
58
32