Unique Permutations via Prefix Reversals

Given a string s, you can perform the following operation any number of times: choose any prefix (i.e., the first k characters) of the string and reverse it. It can be proven that by repeatedly applying this operation, it is possible to generate all distinct permutations of s.

Your task is to compute the number of unique strings (permutations) that can be generated from s using the allowed operation. Two strings are considered different if they differ in at least one position.

The answer is given by the formula: $$\frac{n!}{\prod_{c} (freq(c)!)}$$, where n is the length of s and freq(c) is the frequency of character c in s.

inputFormat

The first line of input contains an integer T, representing the number of test cases.

Each of the following T lines contains a single string s.

outputFormat

For each test case, output a single line containing the number of unique strings that can be generated from s using the allowed operations.

## sample

4
abc
aab
abcd
a

6
3
24
1

</p>