Distinct Palindromic Permutations

You are given a string and you need to determine the number of distinct palindromic permutations that can be formed using all the characters of the string. A palindromic permutation is possible if and only if the number of characters with an odd frequency is at most 1. In mathematical terms, given the frequency counts \(f_i\) of each character, a palindrome permutation can be formed if \(\sum_{i} I(f_i \% 2 \neq 0) \leq 1\). Once it is possible, the number of distinct palindromic permutations is computed as:

\[ \frac{n!}{\prod_{i} (f_i')!} \]

where \(n\) is the sum of half the counts, i.e. \(n = \sum_{i} \frac{f_i}{2}\), and \(f_i' = \frac{f_i}{2}\) for each character.

Your task is to process multiple test cases. For each test case, output the number of distinct palindromic permutations possible for the given string. If no palindromic permutation is possible, output 0.

inputFormat

The first line contains an integer T representing the number of test cases. Each of the following T lines contains a single non-empty string.

outputFormat

For each test case, output a single integer representing the number of distinct palindromic permutations, each on its own line.

## sample

5
aabb
abc
aaa
aaabb
ab

2
0
1
2
0

</p>