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.