Unique Palindromic Permutations

In this problem, you are given a word, and your task is to generate all unique permutations of the word and count how many of these permutations are palindromes. A palindrome is a string that reads the same forwards and backwards, for example, (aba) or (racecar). You need to process multiple test cases by reading input from standard input and output the results to standard output.

inputFormat

The first line of input contains an integer (T) denoting the number of test cases. Each of the following (T) lines contains a single word. The word may include only alphabetic characters.

outputFormat

For each test case, print a single integer on a new line representing the count of unique palindromic permutations of the given word.## sample

3
aab
racecar
abc

1
6
0