Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4026
Magic 12 Months

Time Limit: 1 Second      Memory Limit: 65536 KB

It's New Year's Eve, and it's also the best time of the year to play the card game Magic 12 Months to pray for good luck of the coming year. BaoBao has just found a deck of standard 52 playing cards (without Jokers) in his pocket and decides to play the game. The rules are as follows:

  1. Setup

    1. Remove the four 'K's from the 52 cards.

    2. Shuffle the remaining 48 cards and divide them face down into 12 piles (4 cards per pile) with equal probability.

  2. Gameplay

    1. Let $p = 1$.

    2. Flip the card on the top of the $p$-th pile, check its rank $r$, and discard the card.

    3. If $r$ is a number, let $p = r$; If $r = \text{'A'}$, let $p = 1$; If $r = \text{'J'}$, let $p = 11$; If $r = \text{'Q'}$, let $p = 12$.

    4. If the $p$-th pile is empty, the game ends; Otherwise go back to step 2.2.

When the game ends, having all the 4 cards of rank $m$ flipped and discarded indicates that the $m$-th month in the coming year is a lucky month.

BaoBao is in the middle of the game and has discarded $n$ cards. He wants to know the probability that the $i$-th month of the coming year is a lucky month for all $1 \le i \le 12$ when the game ends. Given these $n$ cards, please help him calculate the answer.

Input

There are multiple test cases. The first line of input contains an integer $T$ (about 100) -- the number of test cases. For each test case:

The first and only line contains an integer $n$ ($0 \le n \le 48$) -- the number of flipped cards, followed by the rank of the $n$ cards $r_1, r_2, \dots, r_n$ ($r_i \in \{\text{A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q}\}$) separated by a space in the order they are flipped. It's guaranteed that the input describes a valid and possible situation of the game.

Output

For each test case output one line containing 12 numbers separated by a space, where the $i$-th number indicates the probability that the $i$-th month of the coming year is a lucky month.

You should output a probability in its simplest fraction form $A/B$ where $A$ and $B$ are coprime. Specifically, if the probability equals 0, you should output 0; If the probability equals 1, you should output 1.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

Sample Input

3
30 9 Q 10 J Q 10 J 10 J J 8 5 7 6 5 7 6 7 6 6 3 A 2 4 A 2 4 2 4 4
0
7 2 A 3 A 4 A A

Sample Output

1 2/3 2/5 1 1/2 1 2/3 2/5 2/5 2/3 1 1/2
1 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2
1 0 0 0 0 0 0 0 0 0 0 0

Author: WANG, Yucheng
Source: The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status