Si una cadena se puede dividir en la forma $AABB$, donde $A$ y $B$ son cadenas no vacías cualesquiera, llamamos excelente a esa división.

Por ejemplo, para la cadena aabaabaa, tomando $A=\texttt{aab}$ y $B=\texttt{a}$ obtenemos una forma de dividirla como $AABB$.

Una cadena puede no tener ninguna división excelente o tener más de una. Por ejemplo, si tomamos $A=\texttt{a}$ y $B=\texttt{baa}$, también expresamos la cadena anterior como $AABB$. En cambio, la cadena abaabaa no tiene ninguna división excelente.

Dada una cadena $S$ de longitud $n$, calcula el número total de divisiones excelentes entre todas las formas de dividir todas sus subcadenas. Una subcadena es un segmento contiguo de una cadena.

Ten en cuenta lo siguiente:

1. Consideramos diferentes las subcadenas iguales que aparecen en posiciones distintas. Las divisiones excelentes de todas ellas cuentan para la respuesta.
2. En una división se permite $A=B$. Por ejemplo, cccc admite la división $A=B=\texttt{c}$.
3. La propia cadena también es una subcadena de sí misma.

Entrada

El archivo de entrada es excellent.in.

Cada archivo contiene varios casos de prueba. La primera línea contiene un único entero $T$, el número de casos. Se garantiza que $1\le T\le10$.

Cada una de las siguientes $T$ líneas contiene una cadena $S$ formada únicamente por letras minúsculas inglesas, con el significado descrito en el enunciado.

Salida

El archivo de salida es excellent.out.

Escribe $T$ líneas con un entero cada una: el número total de divisiones excelentes entre todas las formas de dividir todas las subcadenas de $S$.

Ejemplos

Entrada 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Salida 1

3
5
4
7

Nota

Escribimos $S[i,j]$ para la subcadena que va del carácter $i$ al carácter $j$ de $S$, contando desde $1$.

En el primer caso, hay tres subcadenas con divisiones excelentes:

$S[1,4]=\texttt{aabb}$, con la división excelente $A=\texttt{a}$, $B=\texttt{b}$.

$S[3,6]=\texttt{bbbb}$, con la división excelente $A=\texttt{b}$, $B=\texttt{b}$.

$S[1,6]=\texttt{aabbbb}$, con la división excelente $A=\texttt{a}$, $B=\texttt{bb}$.

Las demás subcadenas no tienen divisiones excelentes, así que la respuesta del primer caso es 3.

En el segundo caso hay dos categorías, con cuatro subcadenas que tienen divisiones excelentes en total:

Las subcadenas $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$ tienen la misma división excelente, $A=\texttt{c}$, $B=\texttt{c}$. Pero, como aparecen en posiciones distintas, se cuenta tres veces.

La subcadena $S[1,6]=\texttt{cccccc}$ tiene dos divisiones excelentes: $A=\texttt{c}$, $B=\texttt{cc}$ y $A=\texttt{cc}$, $B=\texttt{c}$. Son divisiones distintas de una misma subcadena y ambas cuentan para la respuesta.

Por tanto, la respuesta del segundo caso es $3+2=5$.

En el tercer caso, $S[1,8]$ y $S[4,11]$ tienen dos divisiones excelentes cada una. La subcadena $S[1,8]$ es el ejemplo de la descripción del problema, por lo que la respuesta es $2+2=4$.

En el cuarto caso, $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$ y $S[1,8]$ tienen una división excelente cada una, y $S[3,14]$ tiene dos. Por tanto, la respuesta es $5+2=7$.

Ejemplo 2

Consulta excellent/excellent2.in y excellent/excellent2.ans en el directorio de los participantes.

Ejemplo 3

Consulta excellent/excellent3.in y excellent/excellent3.ans en el directorio de los participantes.

Subtareas

Para todos los casos de prueba se garantiza que $1\le T\le10$. Las restricciones siguientes se aplican a cada instancia de entrada individual: las $T$ instancias de un mismo caso de prueba satisfacen las restricciones.

Sea $n$ la longitud de la cadena $S$. Los límites específicos de cada caso de prueba son: