Little C has just finished learning about string matching, and he is practicing now.

For a string ~S~, the question asks him to find the number of ways to split ~S~ in the following form:

~S = ABC~, ~S = ABABC~, ~S = ABAB \dots ABC~, where ~A~, ~B~, ~C~ are all non-empty strings. The number of characters appearing an odd number of times in ~A~ will not be more than the number of characters appearing an odd number of times in ~C~.

More specifically, we can define ~AB~ to represent the concatenation of two strings ~A~ and ~B~. For example ~A = \texttt{aab}~, ~B = \texttt{ab}~, then ~AB = \texttt{aabab}~.

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

Little C's problem is asking to find the number of ways of ~S = (AB)^i C~, where ~F(A) \le F(C)~; ~F(S)~ represents the number of characters that appear an odd number of times in ~S~. Two ways are considered different if and only if at least one string in the split ~A~, ~B~ and ~C~ is different.

Little C doesn't know how to solve this problem, so he asked you for help.

Input Specification

A positive integer ~T~ in the first line of the input file represents the number of data sets in the input.

The next ~T~ lines contain a string ~S~ for each data set on each line. ~S~ consisting of lowercase letters only.

Output Specification

For each data set, output a line with one integer indicating the answer.

Sample Input 1

3
nnrnnr
zzzaab
mmlmmlo

Sample Output 1

8
9
16

Explanation for Sample 1

All possible ways 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}~.

Sample Input 2

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

Sample Output 2

156
138
138
147
194

Additional Samples

Additional samples can be found here.

• Sample 3 (string3.in and string3.ans).
• Sample 4 (string4.in and string4.ans).

Constraints

Test Case	~\vert S \vert \le~	Additional Constraints
~1 \sim 4~	~10~	None
~5 \sim 8~	~100~	None
~9 \sim 12~	~1\,000~	None
~13 \sim 14~	~2^{15}~	~S~ contains only one character
~15 \sim 17~	~2^{16}~	~S~ contains only two characters
~18 \sim 21~	~2^{17}~	None
~22 \sim 25~	~2^{20}~	None

For all test cases, ~1 \le T \le 5~, ~1 \le |S| \le 2^{20}~.

Problem translated to English by Tommy_Shan.