Se uma cadeia puder ser decomposta na forma $AABB$, em que $A$ e $B$ são quaisquer cadeias não vazias, dizemos que essa decomposição da cadeia é excelente.

Por exemplo, para a cadeia aabaabaa, se escolhermos $A=\texttt{aab}$ e $B=\texttt{a}$, encontramos uma forma de a decompor em $AABB$.

Uma cadeia pode não ter nenhuma decomposição excelente ou pode ter mais de uma. Por exemplo, escolhendo $A=\texttt{a}$ e $B=\texttt{baa}$, também podemos representar a cadeia acima na forma $AABB$; porém, a cadeia abaabaa não tem nenhuma decomposição excelente.

É dada uma cadeia $S$ de comprimento $n$. Precisamos de determinar o número total de decomposições excelentes entre todas as decomposições de todas as suas subcadeias. Aqui, uma subcadeia é um segmento contíguo de uma cadeia.

Tem em atenção os pontos seguintes:

1. Subcadeias iguais que aparecem em posições diferentes são consideradas subcadeias diferentes, e as decomposições excelentes de todas elas são contabilizadas na resposta.
2. É permitido ter $A=B$ numa decomposição. Por exemplo, cccc tem a decomposição $A=B=\texttt{c}$.
3. A própria cadeia também é uma subcadeia de si mesma.

Entrada

O ficheiro de entrada é excellent.in.

Cada ficheiro de entrada contém vários casos. A primeira linha contém apenas um inteiro $T$, o número de casos. É garantido que $1\le T\le10$.

Cada uma das $T$ linhas seguintes contém uma cadeia $S$ constituída apenas por letras minúsculas inglesas, com o significado descrito no enunciado.

Saída

O ficheiro de saída é excellent.out.

Imprima $T$ linhas, cada uma contendo um inteiro: o número total de decomposições excelentes entre todas as decomposições de todas as subcadeias da cadeia $S$.

Exemplos

Entrada 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Saída 1

3
5
4
7

Nota

Usamos $S[i,j]$ para representar a subcadeia de $S$ que vai do caráter $i$ ao caráter $j$ (com índices a começar em $1$).

No primeiro caso, existem três subcadeias com decomposições excelentes:

$S[1,4]=\texttt{aabb}$, com a decomposição excelente $A=\texttt{a}$, $B=\texttt{b}$;

$S[3,6]=\texttt{bbbb}$, com a decomposição excelente $A=\texttt{b}$, $B=\texttt{b}$;

$S[1,6]=\texttt{aabbbb}$, com a decomposição excelente $A=\texttt{a}$, $B=\texttt{bb}$.

As restantes subcadeias não têm decomposições excelentes, pelo que a resposta ao primeiro caso é $3$.

No segundo caso, existem duas categorias, num total de quatro subcadeias com decomposições excelentes:

As subcadeias $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$ têm todas a mesma decomposição excelente, $A=\texttt{c}$, $B=\texttt{c}$. Como se encontram em posições diferentes, é necessário contabilizá-la três vezes;

A subcadeia $S[1,6]=\texttt{cccccc}$ tem duas decomposições excelentes: $A=\texttt{c}$, $B=\texttt{cc}$ e $A=\texttt{cc}$, $B=\texttt{c}$. São decomposições diferentes da mesma subcadeia e ambas devem ser contabilizadas na resposta.

Assim, a resposta ao segundo caso é $3+2=5$.

No terceiro caso, $S[1,8]$ e $S[4,11]$ têm, cada uma, duas decomposições excelentes. A subcadeia $S[1,8]$ é o exemplo da descrição do problema, pelo que a resposta é $2+2=4$.

No quarto caso, $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$ e $S[1,8]$ têm, cada uma, uma decomposição excelente, e $S[3,14]$ tem duas. Assim, a resposta é $5+2=7$.

Exemplo 2: entrada e saída

Consulte excellent/excellent2.in e excellent/excellent2.ans no diretório do participante.

Exemplo 3: entrada e saída

Consulte excellent/excellent3.in e excellent/excellent3.ans no diretório do participante.

Subtarefas

Para todos os casos de teste, é garantido que $1\le T\le10$. As restrições seguintes aplicam-se a cada caso de entrada individualmente; ou seja, os $T$ casos de entrada de um mesmo caso de teste satisfazem todos as restrições.

Seja $n$ o comprimento da cadeia $S$. As restrições detalhadas de cada caso de teste encontram-se na tabela seguinte: