Description

If a string can be split into the form $\text{AABB}$, where $\text{A}$ and $\text{B}$ are any non-empty strings, then we call this split of the string excellent. For example, for the string $\texttt{aabaabaa}$, if we set $\text{A}=\texttt{aab}$ and $\text{B}=\texttt{a}$, we have found one way to split this string into $\text{AABB}$.

A string may have no excellent split, or it may have more than one excellent split. For example, if we set $\text{A}=\texttt{a}$ and $\text{B}=\texttt{baa}$, the above string can also be expressed as $\text{AABB}$; however, the string $\texttt{abaabaa}$ has no excellent split.

Now given a string $S$ of length $n$, we need to count, over all substrings of $S$ and all their possible splits, the total number of excellent splits. Here a substring refers to a contiguous segment of the string.

Notes:

1. Identical substrings that appear at different positions are considered different substrings, and their excellent splits are all counted in the answer.
2. In a split, $\text{A}=\text{B}$ is allowed. For example, $\texttt{cccc}$ has the split $\text{A}=\text{B}=\texttt{c}$.
3. The string itself is also one of its substrings.

Input Format

Each input file contains multiple test cases.

The first line of the input file contains a single integer $T$, indicating the number of test cases.

Then follow $T$ lines, each containing a string $S$ consisting only of lowercase English letters, as described above.

Output Format

Output $T$ lines. Each line contains an integer, indicating the total number of excellent splits among all splits of all substrings of $S$.

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

3
5
4
7

Hint

Sample explanation.

We use $S[i, j]$ to denote the substring of $S$ from the $i$-th character to the $j$-th character (1-based indexing).

In the first dataset, there are three substrings with excellent splits: $S[1,4]=\texttt{aabb}$, whose excellent split is $\text{A}=\texttt{a}$, $\text{B}=\texttt{b}$; $S[3,6]=\texttt{bbbb}$, whose excellent split is $\text{A}=\texttt{b}$, $\text{B}=\texttt{b}$; $S[1,6]=\texttt{aabbbb}$, whose excellent split is $\text{A}=\texttt{a}$, $\text{B}=\texttt{bb}$. The remaining substrings have no excellent splits, so the answer for the first dataset is $3$.

In the second dataset, there are in total four substrings that have excellent splits, divided into two types: for the substrings $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$, they share the same excellent split $\text{A}=\texttt{c}$, $\text{B}=\texttt{c}$, but since these substrings are at different positions, they are counted three times; for the substring $S[1,6]=\texttt{cccccc}$, it has two excellent splits: $\text{A}=\texttt{c}$, $\text{B}=\texttt{cc}$ and $\text{A}=\texttt{cc}$, $\text{B}=\texttt{c}$, which are different splits of the same substring and are both counted. Therefore, the answer for the second dataset is $3+2=5$.

In the third dataset, $S[1,8]$ and $S[4,11]$ each have two excellent splits. Among them, $S[1,8]$ is the example in the problem statement, so the answer is $2+2=4$.

In the fourth dataset, $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$, and $S[1,8]$ each have one excellent split, while $S[3,14]$ has two excellent splits, so the answer is $5+2=7$.

Constraints

For all test points, it is guaranteed that $1 \leq T \leq 10$. The following limits apply to a single input within a dataset; that is, within the same test point, all of its $T$ datasets satisfy the constraints.

Let $n$ be the length of string $S$. The detailed constraints for each test point are shown in the table below:

::cute-table{tuack}

Translated by ChatGPT 5