4.2 Enthusiastic Kevin

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

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.

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

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

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

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