Problem Description

Little C has finished studying string matching and is now working on an exercise.

For a string \( S \), the problem requires him to find the number of all possible split schemes of the following form:

\( S = ABC \), \( S = ABABC \), \( S = ABAB \ldots ABC \), where \( A \), \( B \), and \( C \) are non-empty strings, and the number of characters that appear an odd number of times in \( A \) does not exceed 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 recursively define \( A^1 = A \) and \( A^n = A^{n-1} A \) (where \( n \geq 2 \) and is a positive integer). For example, if \( A = \texttt{abb} \), then \( A^3 = \texttt{abbabbabb} \).

Thus, Little C's exercise is to find the number of schemes for \( S = (AB)^iC \) where \( F(A) \leq F(C) \), and \( F(S) \) represents the number of characters that appear an odd number of times in string \( S \). Two schemes are considered different if and only if at least one of the split strings \( A \), \( B \), or \( C \) is different.

Little C doesn't know how to solve this problem and turns to you for help. Please help him.

Input Format

The input contains multiple sets of data. The first line of the input file is a positive integer \( T \) representing the number of data sets.

Each set of data consists of a single line containing a string \( S \), as described in the problem. \( S \) consists only of lowercase English letters.

Output Format

For each set of data, output a single integer representing the answer.

Sample Input and Output

Sample Input #1

3
nnrnnr
zzzaab
mmlmmlo

Sample Output #1

8
9
16

Sample Input #2

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

Sample Output #2

156
138
138
147
194

Sample Input #3

See attachment string/string3.in

Sample Output #3

See attachment string/string3.ans

Sample Input #4

See attachment string/string4.in

Sample Output #4

See attachment string/string4.ans

Notes/Hints

[Sample #1 Explanation]

For the first set of data, all the schemes 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} \).

[Data Range]

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

见题面 Input 部分

见题面 Output 部分