Si une chaîne peut être décomposée sous la forme $AABB$, où $A$ et $B$ sont des chaînes quelconques non vides, nous qualifions cette décomposition d'excellente.

Par exemple, pour la chaîne aabaabaa, choisir $A=\texttt{aab}$ et $B=\texttt{a}$ donne une décomposition sous la forme $AABB$.

Une chaîne peut n'avoir aucune décomposition excellente ou en avoir plusieurs. Par exemple, en choisissant $A=\texttt{a}$ et $B=\texttt{baa}$, on peut aussi représenter la chaîne précédente sous la forme $AABB$ ; en revanche, la chaîne aababaa n'a aucune décomposition excellente.

Étant donnée une chaîne $S$ de longueur $n$, nous souhaitons déterminer le nombre total de décompositions excellentes parmi toutes les décompositions de toutes ses sous-chaînes. Ici, une sous-chaîne désigne une portion contiguë de la chaîne.

Les points suivants sont à noter :

1. Deux sous-chaînes identiques situées à des positions différentes sont considérées comme différentes ; leurs décompositions excellentes sont toutes comptées dans la réponse.
2. Une décomposition peut avoir $A=B$. Par exemple, cccc admet la décomposition $A=B=\texttt{c}$.
3. La chaîne elle-même est aussi l'une de ses sous-chaînes.

Entrée

Le fichier d'entrée est excellent.in.

Chaque fichier d'entrée contient plusieurs jeux de données. Sa première ligne contient un seul entier $T$, le nombre de jeux de données. Il est garanti que $1\le T\le10$.

Chacune des $T$ lignes suivantes contient une chaîne $S$ composée uniquement de lettres minuscules de l'alphabet anglais, dont la signification est celle de l'énoncé.

Sortie

Le fichier de sortie est excellent.out.

Afficher $T$ lignes contenant chacune un entier : le nombre total de décompositions excellentes parmi toutes les décompositions de toutes les sous-chaînes de $S$.

Exemples

Entrée 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Sortie 1

3
5
4
7

Remarque

Nous notons $S[i,j]$ la sous-chaîne de $S$ allant du $i$-ème au $j$-ème caractère, les positions étant numérotées à partir de $1$.

Dans le premier jeu de données, trois sous-chaînes admettent une décomposition excellente :

$S[1,4]=\texttt{aabb}$, avec la décomposition excellente $A=\texttt{a}$, $B=\texttt{b}$ ;

$S[3,6]=\texttt{bbbb}$, avec la décomposition excellente $A=\texttt{b}$, $B=\texttt{b}$ ;

$S[1,6]=\texttt{aabbbb}$, avec la décomposition excellente $A=\texttt{a}$, $B=\texttt{bb}$.

Les autres sous-chaînes n'admettent aucune décomposition excellente ; la réponse pour le premier jeu de données est donc $3$.

Dans le deuxième jeu de données, quatre sous-chaînes, réparties en deux catégories, admettent des décompositions excellentes :

Les sous-chaînes $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$ ont toutes la même décomposition excellente, $A=\texttt{c}$, $B=\texttt{c}$. Comme elles occupent des positions différentes, elle doit être comptée trois fois.

La sous-chaîne $S[1,6]=\texttt{cccccc}$ a deux décompositions excellentes : $A=\texttt{c}$, $B=\texttt{cc}$ et $A=\texttt{cc}$, $B=\texttt{c}$. Ce sont des décompositions différentes d'une même sous-chaîne, et toutes deux doivent être comptées dans la réponse.

La réponse pour le deuxième jeu de données est donc $3+2=5$.

Dans le troisième jeu de données, $S[1,8]$ et $S[4,11]$ ont chacune deux décompositions excellentes. $S[1,8]$ est l'exemple donné dans l'énoncé ; la réponse est donc $2+2=4$.

Dans le quatrième jeu de données, $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$, $S[1,8]$ ont chacune une décomposition excellente, et $S[3,14]$ en a deux ; la réponse est donc $5+2=7$.

Exemple 2

Voir les fichiers excellent/excellent2.in et excellent/excellent2.ans dans le répertoire des candidats.

Exemple 3

Voir les fichiers excellent/excellent3.in et excellent/excellent3.ans dans le répertoire des candidats.

Sous-tâches

Pour tous les tests, $1\le T\le10$. Les restrictions ci-dessous s'appliquent à un seul jeu de données : les $T$ jeux de données d'un même test respectent toutes ces restrictions.

Notons $n$ la longueur de la chaîne $S$. Les contraintes détaillées de chaque test sont données dans le tableau suivant :