Little Cyan Fish aime beaucoup la théorie des chaînes de caractères. Aujourd'hui, Little Cyan Fish vous invite à étudier les surnoms humains avec lui.

Dans l'univers de Little Cyan Fish, les surnoms humains peuvent tous être représentés par une chaîne contenant uniquement des lettres latines minuscules (a à z). Par exemple, "qingyu" et "xiuga" sont des surnoms humains, mais "Abacde" n'est pas un surnom humain.

Little Cyan Fish considère qu'un nom $s$ est de Lyndon si et seulement si pour chaque suffixe propre* $t$ de $s$, l'ordre lexicographique de $s$ est strictement inférieur à celui de $t$. Par exemple, "abacde" est une chaîne de Lyndon, mais "qingyu" n'est pas une chaîne de Lyndon (car la chaîne d'origine n'est pas lexicographiquement inférieure au suffixe propre "ingyu").

Maintenant, Little Cyan Fish vous donne un surnom humain $s$, et vous devez calculer combien il existe de paires différentes $(l, r)$ avec $1 \le l \le r \le |s|$ telles que $s[l \dots r]$ soit de Lyndon.

* Un suffixe propre est un suffixe non vide qui n'est pas égal à la chaîne d'origine. Par exemple, "qqoj" possède $3$ suffixes propres, qui sont "j", "oj" et "qoj".

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, l'entrée contient une seule ligne avec une chaîne $s$ ($1 \le |s| \le 2 \times 10^5$), indiquant le surnom humain.

Il est garanti que la somme de $|s|$ sur tous les cas de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un entier, indiquant la réponse.

Exemple

Entrée 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Sortie 1

3
9
27
16
58
32