4.2 Enthusiastic Kevin
(RankList for this Question)
Score: 60pts
Time Limit: 5.00 sec
Kevin is an enthusiast and likes to explore new things. So, one day he was sitting and thought about what ternary strings are and learnt about them. Then he started exploring many such strings and wondered for any given ternary string K of length N consisting of 0, 1, and 2 Is it possible to determine the number of distinct permutations of K for which satisfies the below condition:

Let R be the permutation of K, R is valid if the count of all palindromic substrings (sizes from 1 to N) does not exceed N

Constraints
1≤T≤20000
1≤N≤200000
The sum of the length of strings over all test cases does not exceed 200000.

Input Format
The first line contains an integer denoting the number of test cases T
The first line of each test case contains a ternary string S

Output Format
Print T lines. For each test case:
Print a single line indicating the number of ways to rearrange S such that the number of palindromes does not exceed N

Example 1
Input:
2
201
22011

Output:
6
2

Explanation:
First test case: All the permutations of this string are different and valid.
"012","021","102","120","210" and "201".