Problem Description

After learning about string matching, Little C is now working on a problem.

For a string $S$, the task asks him to find the number of all split plans of $S$ that have one of the following forms:

$S = ABC$, $S = ABABC$, $S = ABAB \ldots ABC$, where $A$, $B$, and $C$ are all non-empty strings, and the number of characters that appear an odd number of times in $A$ is not greater than the number of characters that appear an odd number of times in $C$.

More specifically, we define $AB$ as the concatenation of two strings $A$ and $B$. For example, if $A = \texttt{aab}$ and $B = \texttt{ab}$, then $AB = \texttt{aabab}$.

We also define recursively $A^1 = A$ and $A^n = A^{n - 1} A$ ($n \ge 2$ and $n$ is a positive integer). For example, if $A = \texttt{abb}$, then $A^3 = \texttt{abbabbabb}$.

Then Little C's exercise is to find the number of plans such that $S = {(AB)}^i C$, where $F(A) \le F(C)$. Here, $F(S)$ denotes the number of characters that appear an odd number of times in the string $S$. Two plans are different if and only if at least one of the split strings $A$, $B$, and $C$ is different.

Little C cannot solve this problem, so he asks you for help. Please help him.

Input Format

This problem contains multiple test cases. The first line of the input file contains a positive integer $T$, indicating the number of test cases.

Each test case contains one line with a string $S$, as described above. $S$ consists only of lowercase English letters.

Output Format

For each test case, output one integer per line, representing the answer.

3
nnrnnr
zzzaab
mmlmmlo

8
9
16

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

156
138
138
147
194

见附件中的 string/string3.in

见附件中的 string/string3.ans

见附件中的 string/string4.in

见附件中的 string/string4.ans

Hint

【Sample #1 Explanation】

For the first test case, all valid plans are:

1. $A = \texttt{n}$, $B = \texttt{nr}$, $C = \texttt{nnr}$.
2. $A = \texttt{n}$, $B = \texttt{nrn}$, $C = \texttt{nr}$.
3. $A = \texttt{n}$, $B = \texttt{nrnn}$, $C = \texttt{r}$.
4. $A = \texttt{nn}$, $B = \texttt{r}$, $C = \texttt{nnr}$.
5. $A = \texttt{nn}$, $B = \texttt{rn}$, $C = \texttt{nr}$.
6. $A = \texttt{nn}$, $B = \texttt{rnn}$, $C = \texttt{r}$.
7. $A = \texttt{nnr}$, $B = \texttt{n}$, $C = \texttt{nr}$.
8. $A = \texttt{nnr}$, $B = \texttt{nn}$, $C = \texttt{r}$.

【Constraints】

For all test points, it is guaranteed that $1 \le T \le 5$ and $1 \le |S| \le 2^{20}$.

Translated by ChatGPT 5