Bring Bring Big Teacher Brother

"Why are you shouting so loudly? Why don't you go to the property control? You try roar again?!"

After the gentle and easy-going Master Sun uttered a lot of adrenaline-provoking words, people did not hate him at all, but liked him more. His paragraph became a source of happiness for people. For example, his idea about meeting and working is very famous: "When the meeting is so serious, everyone is being scolded, how can you laugh when everyone is accepting opinions.Should I smile?smile to the death photo of your horse ".


Later, the Master Sun became an indispensable part of people's life, and people consider what he said an abstract Bible.

definition:
If the substring $s[l .. r]$ of a string s is an abstract Bible, if and only if $l = r$ or satisfies the following conditions:

1. $mid$ is an integer, and the character s[mid] appears only once in $s[l .. r]$. (where mid is defined as $\frac{(l+r)}{2}$ )

2. $s[l .. mid-1] = s[mid + 1 .. r]$.

3. $s[l .. mid-1]$ is also an abstract Bible.

Now, given a string s, the happy value of this string is

$$\sum_{l=1}^{\left|s \right|} \sum_{r=l}^{\left|s \right|} G(s[l..r])\times (r-l+1)^2$$

Where $G(t)=1$ if and only if t is an abstract Bible, otherwise $G(t)=0$.


On this day, Mr. Sun is interacting with his neighbour's softly and gently. Every word he says has been all memorized by you. Let's call it string s. You want to quote classics to the people around you. But quoting classics is not equivalent to copying. So you want to know how much happy value can be brought by changing at most one character of the original string s.

First line containing single integer T representing testcase number.
Next T lines each line containing a string.

$|s| \leq 10^5$, s only contain lowercase letter.

T lines,each line one integer representing the answer.

2
abacaba
zyz

83
12

substring
[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[1,3],[3,5],[5,7],[1,7] are abstract bible.
Answer = 1 * 7 + 9 + 9 + 9 + 49 = 83
It can be proved that you can't modify any letter such that a better result is procedured.

2019中山大学程序设计竞赛（重现赛）