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

For a string $S$, the problem asks him to find the number of ways to split $S$ into the following form: $S = ABC$, $S = ABABC$, $S = ABAB \cdots ABC$, where $A, B, C$ are all non-empty strings, and the number of characters appearing an odd number of times in $A$ is no more than the number of characters appearing an odd number of times in $C$.

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

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

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

Little C does not know how to solve this problem and is asking for your help. Please help him.

Input

The input is read from the file string.in.

There are multiple test cases. The first line of the input file contains a positive integer $T$, representing the number of test cases.

Each test case consists of a single line containing a string $S$. See the problem description for its meaning. $S$ consists only of lowercase English letters.

Output

The output is written to the file string.out.

For each test case, output a single integer on a line representing the answer.

Examples

Input 1

3
nnrnnr
zzzaab
mmlmmlo

Output 1

8
9
16

Note 1

For the first test case, all possible ways are: 1. $A=\text{n}$, $B=\text{nr}$, $C=\text{nnr}$. 2. $A=\text{n}$, $B=\text{nrn}$, $C=\text{nr}$. 3. $A=\text{n}$, $B=\text{nrnn}$, $C=\text{r}$. 4. $A=\text{nn}$, $B=\text{r}$, $C=\text{nnr}$. 5. $A=\text{nn}$, $B=\text{rn}$, $C=\text{nr}$. 6. $A=\text{nn}$, $B=\text{rnn}$, $C=\text{r}$. 7. $A=\text{nnr}$, $B=\text{n}$, $C=\text{nr}$. 8. $A=\text{nnr}$, $B=\text{nn}$, $C=\text{r}$.

Input 2

5
kkkkkkkkkkkkkkkkkkkk
llllllllllllrrlllrr
ccccccccccccxcxxxcc
cccccccccccccaababa
gggggggggggggbaabab

Output 2

156
138
138
147
194

Examples 3 and 4

See string/string3.in and string/string3.ans, and string/string4.in and string/string4.ans in the contestant's directory.

Constraints

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