You are given a ternary string $S$ of length $N$ consisting of 0, 1, and 2. Your task is to determine the number of distinct permutations of $S$ for which satisfies the below condition:

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

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$.

Constraints

$1 \leq T \leq 20000$

$1 \leq N \leq 200000$

The sum of the length of strings over all test cases does not exceed 200000.