G. PokerStars
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The PokerStars team has came up with a new form of poker. They weren't very original so it is almost like Texas Hold'em but each player receives $$$5$$$ cards and there are only $$$2$$$ cards on the table (do not worry, the rules will be explained in more detail below).

They want to inaugurate it with a broadcasted competition but they need something from you. In order to make it more interesting for the viewers they want to show them the probability of each player of winning after all of them received their cards. Can you help them?

Game Rules :

  • The game is played with a normal pack of $$$52$$$ cards - each card has a rank ($$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, $$$9$$$, $$$10$$$, $$$J$$$, $$$Q$$$, $$$K$$$, $$$A$$$) with A being the highest and 2 the lowest and a suit ($$$clubs$$$, $$$diamonds$$$, $$$hearts$$$, $$$spades$$$).
  • Each player receives $$$5$$$ cards and after that there are put $$$2$$$ cards on the table.
  • With the cards in the hand and the ones on the table each player has to choose $$$5$$$ of them that represent his best poker hand.

Poker Hands (from the highest to the lowest) :

  • Royal flush - [$$$A, K, Q, J, 10$$$] all the same suit.
  • Straight flush - Five cards in a sequence, all in the same suit (both [$$$5, 4, 3, 2, A$$$] and [$$$A, K, Q, J, 10$$$] are valid).
  • Four of a kind - All four cards of the same rank.
  • Full house - Three of a kind with a pair.
  • Flush - Any five cards of the same suit, but not in a sequence.
  • Straight - Five cards in a sequence, but not of the same suit (both [$$$5, 4, 3, 2, A$$$] and [$$$A, K, Q, J, 10$$$] are valid).
  • Three of a kind - Three cards of the same rank.
  • Two pair - Two different pairs.
  • Pair - Two cards of the same rank.
  • High card - When you haven't made any of the hands above, the highest card plays.

If 2 players have the same type of hand :

  • Royal flush - Nothing to do here.
  • Straight flush - The one with the higher high card from the straight flush wins (for example, if player $$$1$$$ has [$$$5, 4, 3, 2, A$$$] and player $$$2$$$ has [$$$8, 7, 6, 5, 4$$$] than player $$$2$$$ wins).
  • Four of a kind - The player with the higher four of a kind wins.
  • Full house - the player with the higher three of a kind wins. If they are identical, the player with the higher pair wins.
  • Flush - The player with the highest card in the flush wins. If they are identical, the second highest card decides, then the third highest, then the fourth and then the fifth. The suit of the flush does not matter.
  • Straight - The one with the higher high card from the straight wins.
  • Three of a kind - The player with the higher three of a kind wins. If they are identical, the highest kicker wins, then the second highest.
  • Two pair - The player with the higher high pair wins. If they are identical, the player with the higher low pair wins. If they are also identical, the player with the highest kicker wins.
  • Pair - The player with the higher pair wins. If they are identical, the highest kicker wins, then the second highest, then the third highest.
  • High card - The highest card wins. If they are identical, the second highest card decides, then the third, then the fourth, then the fifth.

Note : A kicker is the set of cards in a standard five-card poker hand which are not the part of the hand which makes its rank. The kicker is used to break ties between poker hands of otherwise equivalent rank.

Because the PokerStars team does not like split pots, if after all the criteria above are applied and the $$$2$$$ players are still at a tie, the player with the smallest index wins (formally, player $$$i$$$ beats player $$$j$$$ if $$$i \lt j$$$).

Input

The first line of the input will contain the number $$$T$$$ ($$$1 \leq T \leq 30$$$), representing the number of test cases.

The first line of each test will contain one positive integer $$$N$$$, the number of players.

The next $$$5*N$$$ lines will contain the cards of each player, player $$$i$$$ ($$$1 \leq i \leq N$$$) will have the cards from line $$$(i-1)*5+1$$$ to line $$$(i-1)*5+4$$$.

Each card is represented by $$$2$$$ strings, $$$rank$$$ and $$$suit$$$:

  • $$$rank$$$ is one of the following: $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, $$$9$$$, $$$10$$$, $$$J$$$, $$$Q$$$, $$$K$$$, $$$A$$$.
  • $$$suit$$$ is one of the following: $$$clubs$$$, $$$diamonds$$$, $$$hearts$$$, $$$spades$$$.

It is guaranteed that all cards in a test case are distinct.

Output

The output file should consist of one line for each test case.

Each line should contain $$$N$$$ numbers (where $$$N$$$ is the number of players for each test case), the probabilities of winning the game for each player.

The probability of winning the game for player $$$i$$$ can be expressed by $$$P_i/Q$$$ where $$$P_i$$$ represents the number of cases where player $$$i$$$ wins and $$$Q$$$ represents the number of total cases. You should output the probability of winning the game for player $$$i$$$ as $$$P_i*Q^{-1}$$$ modulo $$$100055128505716009$$$.

Example
Input
1
4
2 clubs
4 diamonds
7 hearts
J spades
Q clubs
2 diamonds
4 hearts
7 spades
J clubs
Q diamonds
2 hearts
4 spades
7 clubs
J diamonds
Q hearts
2 spades
4 clubs
7 diamonds
J hearts
Q spades
Output
1 0 0 0
Note

The example consists of only one test case.

In the example, player 1 wins all the possible outcomes.