If a string can be written in the form of ~\texttt{AABB}~ where ~\texttt{A}~ and ~\texttt{B}~ are arbitrary non-empty strings, then we say this is a good partition. For example, it is possible to write the string ~\texttt{aabaabaa}~ in the form of ~\texttt{AABB}~ by letting ~\texttt{A} = \texttt{aab}~ and ~\texttt{B} = \texttt{a}~.

Some strings do not admit a good partition, while some strings admit multiple good partitions. For example, for the above string ~\texttt{aabaabaa}~, it is also possible to write it in the form of ~\texttt{AABB}~ by letting ~\texttt{A} = a~ and ~\texttt{B} = \texttt{baa}~. The string ~\texttt{abaabaa}~ does not admit good partitions.

Given a string ~S~ of length ~n~, compute the sum, over all its substrings, of the number of good partitions of those substrings. Here, substring refers to a contiguous part of the string.

Please pay attention to the following details:

• The same string appearing at different locations are considered distinct. All good partitions corresponding to the same string should count towards the answer.
• It is possible to have ~\texttt{A} = \texttt{B}~ in a good partition. For example, the string ~\texttt{cccc}~ admits good partition ~\texttt{A} = \texttt{B} = \texttt{c}~.
• The string ~S~ itself is one of its substrings.

Input Specification

Each input file has several test cases.

The first line of the input file contains one integer ~T~ denoting the number of test cases in the file.

In the following ~T~ lines, each line contains a string ~S~ consisting of lower-case English letters.

Output Specification

Output ~T~ lines: each line consists of an integer denoting the total number of good partitions among all possible partitions of substrings of ~S~.

Sample Input 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Sample Output 1

3
5
4
7

Explanation for Sample 1

Let ~S[i,j]~ denote the substring of ~S~ consisting of the ~i~-th character to the ~j~-th character of ~S~, with index starting from ~1~.

In the first test case, there are three substrings admitting good partitions: ~S[1,4] = \texttt{aabb}~ with ~\texttt{A} = \texttt{a}, \texttt{B} = \texttt{b}~, ~S[3,6] = \texttt{bbbb}~ with ~\texttt{A} = \texttt{b}, \texttt{B} = \texttt{b}~, and ~S[1,6] = \texttt{aabbbb}~ with ~\texttt{A} = \texttt{a}, \texttt{B} = \texttt{bb}~. Other substrings of ~S~ do not admit good partitions, so the answer shall be ~3~.

In the second test case, ~S[1,4] = S[2,5] = S[3,6] = \texttt{cccc}~ admit good partition ~\texttt{A} = \texttt{c}, \texttt{B} = \texttt{c}~, so the total contribution to the final answer is ~3~. For string ~S[1,6] = \texttt{cccccc}~, it admits two good partitions (~\texttt{A} = \texttt{c}, \texttt{B} = \texttt{cc}~ or ~\texttt{A} = \texttt{cc}, \texttt{B} = \texttt{c}~). The different good partitions corresponding to the same substring should all count towards the final answer, so the final answer to the second test case is ~3+2 = 5~.

In the third test case, ~S[1,8]~ and ~S[4,11]~ admit two good partitions respectively. ~S[1,8]~ is the example described in the problem description. The answer should be ~2+2 = 4~.

In the fourth test case, each of ~S[1,4], S[6,11], S[7,12], S[2,11], S[1,8]~ admits one good partition, and ~S[3,14]~ admits two good partitions, so the answer should be ~5+2 = 7~.

Attachment Package

The samples are available here.

Sample 2

See ex_excellent2.in and ex_excellent2.ans.

Sample 3

See ex_excellent3.in and ex_excellent3.ans.

Constraints

For all test cases, ~1 \le T \le 10~, ~n \le 30\,000~.

Test case	~n \le~	Special properties
1,2	~300~	All characters of ~S~ are same.
3,4	~2\,000~
5,6	~10~	No additional constraints.
7,8	~20~
9,10	~30~
11,12	~50~
13,14	~100~
15	~200~
16	~300~
17	~500~
18	~1\,000~
19	~2\,000~
20	~30\,000~