Palindromic Permutations

Given a string s, your task is to determine the number of distinct palindromic permutations that can be formed using all the characters of s. A palindromic permutation is a rearrangement of the string such that it reads the same forwards and backwards.

The key idea is that a necessary condition for a palindromic permutation to exist is that at most one character appears an odd number of times. If more than one character has an odd frequency, then no palindromic permutation is possible.

If a palindromic permutation is possible, let each character's frequency be denoted by f_i. Consider using half of each count (i.e., n_i = \lfloor f_i/2 \rfloor) to form one half of the palindrome. The total number of characters in half the palindrome is n = \sum_i n_i, and the number of distinct arrangements is given by the formula:

$$\text{Answer} = \frac{n!}{\prod_{i} (n_i!)}$$

You need to process multiple test cases. For each test case, output the corresponding number of palindromic permutations.

inputFormat

The input is provided via standard input as follows:

1. The first line contains an integer T representing the number of test cases.
2. Each of the following T lines contains a non-empty string s consisting of lowercase Latin letters.

outputFormat

For each test case, output a single integer on a new line, which is the number of distinct palindromic permutations that can be formed from the input string. The answer is computed using the formula:

$$\text{Answer} = \frac{n!}{\prod_{i} (n_i!)}$$

where n = \sum_i n_i and n_i = \lfloor f_i/2 \rfloor for each character frequency fi in the string.

## sample

2
aabb
abc

2
0

</p>