Palindromic Permutations

Given a string w, you are required to determine the number of unique palindromic permutations that can be formed by rearranging its characters. A palindrome is a sequence that reads the same backward as forward. In order to form a palindrome, the frequency of each character must be even, except for at most one character which may appear an odd number of times.

The number of palindromic permutations can be computed using the formula:

[ \frac{\Bigl(\sum_{c}\lfloor f(c)/2 \rfloor\Bigr)!}{\prod_{c}(\lfloor f(c)/2 \rfloor)!} ]

where \(f(c)\) is the frequency of character c in the string.

If it is impossible to form any palindrome then the answer is 0.

inputFormat

The input begins with an integer T (1 \(\leq\) T \(\leq\) 10⁵), denoting the number of test cases. Then, T lines follow where each line contains a string representing the word.

Example Input:

2
 aabb
 abc

outputFormat

For each test case, output the number of unique palindromic permutations that can be formed using all the characters of the given string. Each result should be printed on a new line.

Example Output:

2
0

## sample

2
aabb
abc

2
0

</p>