Background

Dou Dizhu is a card game played with a standard 54-card deck, including the two jokers (small and large). There are four cards of each rank from A to K, and one small joker and one large joker. The rank order is: $3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A < 2 < \text{Small Joker} < \text{Large Joker}$. Suits do not affect the rank. Each game consists of a hand of $n$ cards. Players take turns playing cards according to specific allowed patterns, and the first player to empty their hand wins. To simplify the problem, we ignore suits; all cards of the same rank are considered identical.

In this problem, the allowed card patterns are (note that this differs from traditional Dou Dizhu):

Note:

1. There is no "consecutive bomb" pattern, but a sequence like 444455556666 can be played as an Airplane (Single Wings) of 444555666 with 4, 5, 6 as the wings.
2. The small and large jokers have different ranks, so an airplane with jokers as wings is legal, e.g., 333444♂♀.
3. It is easy to verify that these rules are well-defined, meaning any valid set of cards has a unique pattern.

Two hands belong to the same pattern if and only if they have the same name and the same number of cards. There is a hierarchy within the same pattern (the Rocket is unique and does not need comparison):

1. The rank of a Triple with Single or Triple with Pair depends on the rank of the triple.
2. The rank of an Airplane depends on the rank of the consecutive triples.
3. The rank of a Quad with Two Singles depends on the rank of the four cards.
4. The rank of other patterns depends on the highest-ranking card in the set.

The game process is as follows (this is identical to traditional Dou Dizhu):

1. Players are divided into two camps: one Landlord and two Peasants. The Landlord has 20 cards, and each Peasant has 17 cards (totaling one deck).
2. The game consists of several rounds. The winner of the previous round leads the next (the Landlord leads the first round). Play proceeds in clockwise order.
3. The first player in a round can play any valid pattern. Subsequent players have the following choices:
   1. Pass.
   2. Play a hand of the same pattern with a strictly higher rank.
   3. If the previous hand was not a bomb or rocket, play any bomb.
   4. Play a rocket.
4. If two consecutive players pass after a card is played, the round ends, and the player who played the last card leads the next round.
5. The game ends when a player empties their hand, and that player wins.
6. If the Landlord wins and neither Peasant has played any cards, it is called a "Spring".

Description

Three people are playing Dou Dizhu. If the Landlord achieves a "Spring", the Landlord wins; otherwise, even if the Landlord empties their hand first, the Peasants win. Assume all players act optimally.

Given $n$ ($0 \leq n \leq 20$) cards, how many initial hands for the Landlord contain these $n$ cards such that the Landlord is guaranteed to achieve a "Spring" regardless of the Peasants' cards?

Input

The first line contains an integer $t$, the number of test cases.

Each test case consists of one line. The first integer $n$ is the number of fixed cards, followed by $n$ space-separated integers describing the fixed cards.

Specifically, $1$ represents A, $11$ represents J, $12$ represents Q, $13$ represents K, $14$ represents the small joker, and $15$ represents the large joker. The input is guaranteed to be valid (the count of each card does not exceed the total available in a deck).

Output

For each test case, output an integer representing the number of valid initial hands for the Landlord, modulo $998244353$.

Note: Suits are ignored. If two hands have the same composition of ranks, they are considered identical.

Examples

Input 1

6
20 1 2 2 3 4 5 6 7 8 8 9 10 11 11 12 13 13 13 13 15
20 1 1 2 2 3 4 5 6 7 8 9 10 11 12 12 12 12 13 13 14
20 1 2 2 3 3 4 5 6 7 7 7 7 8 9 10 10 11 12 13 15
20 1 2 3 4 4 5 6 7 8 9 10 11 11 12 13 13 13 13 14 15
3 3 3 3
4 3 3 3 3

Output 1

1
0
1
1
4790
1670

Note 1

For the first example, the Peasants cannot have any bombs or rockets. The Landlord can lead with $[3,4,5,6,7,8,9,10,J,Q]$ (which the Peasants cannot beat), then play $[2,2]$, then the large joker, then $[K,K,K,K,A,J]$, and finally $[8]$.

Subtasks