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

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

, , , where , , are all non-empty strings. The number of characters appearing an odd number of times in will not be more than the number of characters appearing an odd number of times in .

More specifically, we can define to represent the concatenation of two strings and . For example , , then .

We also recursively define , ( and is a positive integer). For example, , then .

Little C's problem is asking to find the number of ways of , where ; represents the number of characters that appear an odd number of times in . Two ways are considered different if and only if at least one string in the split , and is different.

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

#### Input Specification

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

The next lines contain a string for each data set on each line. 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

- , , .
- , , .
- , , .
- , , .
- , , .
- , , .
- , , .
- , , .

#### 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 | Additional Constraints | |
---|---|---|

None | ||

None | ||

None | ||

contains only one character | ||

contains only two characters | ||

None | ||

None |

For all test cases, , .

Problem translated to English by .

## Comments