Mahjong is a traditional game played by 4 players who take turns drawing and discarding tiles. In competitive play, there are two main sets of rules: International Mahjong (China) and Riichi Mahjong (Japan). This problem uses a special set of rules called the "Dora Pile" rules.

Tile Types

A standard set of Mahjong consists of 136 tiles, comprising 34 different types, with 4 tiles of each type. The 34 types are: 1-9 Man (characters), 1-9 Sou (bamboo), 1-9 Pin (dots), East, South, West, North, White, Green, Red.

They can be combined into different patterns: Sequence (Shuntsu): 3 tiles of consecutive numbers in the same suit (Man, Sou, or Pin). Triplet (Koutsu): 3 identical tiles. Quad (Kantsu): 4 identical tiles. Pair (Jantou): 2 identical tiles.

Sequences and triplets are collectively referred to as "melds" (mentsu).

Winning (Agari)

A state where a player's hand is declared a win is called "Agari". When a player holds 14 tiles, they win if one of the following three conditions is met: 1. There exists a configuration where the 14 tiles can be divided into 4 melds and 1 pair, denoted as "34+2". 2. There exists a configuration where the 14 tiles can be divided into 7 distinct pairs, known as "Seven Pairs" (Chiitoitsu). 3. The 14 tiles consist only of the 13 types: 1-9 Man, 1-9 Sou, 1-9 Pin, East, South, West, North, White, Green, Red, and each of these 13 types is present at least once, known as "Thirteen Orphans" (Kokushi Musou).

• When a player holds 15 tiles, they win if there exists a configuration where the 15 tiles can be divided into 1 quad, 3 melds, and 1 pair.
• When a player holds 16 tiles, they win if there exists a configuration where the 16 tiles can be divided into 2 quads, 2 melds, and 1 pair.
• When a player holds 17 tiles, they win if there exists a configuration where the 17 tiles can be divided into 3 quads, 1 meld, and 1 pair.
• When a player holds 18 tiles, they win if there exists a configuration where the 18 tiles can be divided into 4 quads and 1 pair.

Dora Tiles

Each game specifies several "Dora" tiles. When winning, each Dora tile in the hand doubles the payout (detailed below).

Achievement Score

Since there are many possible winning hands, we define an "Achievement Score" for each winning hand. This score is calculated as the number of ways to form the hand by choosing tiles from all remaining undealt tiles, multiplied by $2^k$, where $k$ is the number of Dora tiles in the hand. This score considers both the probability of forming the hand and the payout.

Specifically, for a "Seven Pairs" winning hand, the achievement score is multiplied by 7. For a "Thirteen Orphans" winning hand, the achievement score is multiplied by 13.

One day, players L, Y, I, and W were playing Mahjong. Xueye passed by and saw all the discarded tiles, but did not know any player's hand. She wants to know the maximum "Achievement Score" possible for a winning hand among all remaining undealt tiles.

Input

The input contains multiple test cases. The first line is an integer $T$, the number of test cases. Each test case is independent. Each test case consists of two lines: the first line gives the tiles already discarded on the table, and the second line gives all the Dora tiles for that round. Tiles are represented as: 1m, 2m, ..., 9m for Man; 1p, 2p, ..., 9p for Pin; 1s, 2s, ..., 9s for Sou; E, S, W, N for East, South, West, North; Z, B, F for White, Green, Red. Tiles are separated by spaces, and each line ends with a single 0.

Output

For each test case, output a single integer representing the maximum score.

Examples

Input 1

2
0
0
7m 4p 2s 7s 6p 8s 7p 5s 9s 9s 1p 5m 9m 5s 4p 5s E 1p 6s 
5p B 4m 6m W 6p 6s E 9s 5p 2s 8s 8p 4m 3s 9m 5p 3s 2s 6s 8s 
8p 6p 5m 4s 3m 4s 5s 4s 6m 9s 6p N 5m 7s 4m 2m 2s 6s 3m 7p 
B B N 1m 3m B 8p F 7p 0
W 4p N 3m 2m B 9m 3p 1p 6p S 4s 5p 8s 4m 5s 2s 3s 0

Output 1

1308622848
127401984

Note

In the first test case, no tiles have been discarded and there are no Dora tiles. The "Thirteen Orphans" hand has the highest score, which is $13 \times 6 \times 4^{12}$. The scores for "3*4+2" and "Seven Pairs" are 100663296 and 1959552 respectively.

In the second test case, the "3*4+2" hand has the highest score of 127401984. One such hand is "1m2m3m 7m8m9m 1p2p3p 3p4p5p SS". The score for "Seven Pairs" is 125411328, and "Thirteen Orphans" is impossible.

Constraints

Figure 1. Mahjong tile types and meld patterns