403145: GYM101047 A Bridge

Bridge is a great card game! The 2006 World Youth Team Championship in Bridge took place in Thailand, the same country that will host the 2016 ICPC World Finals! Let's describe the rules of bridge. The game is played with a standard 52-card deck, with 13 cards from each of the four suits (hearts, spades, clubs, and diamonds). The cards are ranked as A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2, with the ace having the highest rank and 2 the lowest. There is also a predetermined trump suit (H = hearts, S = spades, C = clubs, D = diamonds, NT = no trump).

The game is played by 4 players (N, E, S, W), as shown in the figure, and it has several rounds, called tricks. A player starts a round/trick by playing a card. Afterwards, each player plays a card, following clockwise order, until everyone has played. The trick then ends. The leading player in the trick can play whichever card she or he wants; this card's suit is defined as the current trick's suit. Every player other than the leading player must play a card of the same suit as the current trick's, unless she or he has no such card. In this case, the player can play any card.

The winner of a trick is defined as follows. If a trump card (a card of the trump suit) has been played, the winner is the player who played the highest ranking trump card. Otherwise, the winner is the player who played the highest ranking card of the trick's suit. The winner of a trick starts the next trick.

Player N starts the first trick. Players N and S play as a team, as do E and W. The goal is to win the most tricks.

In this problem, each player has R cards and we would like to know how many tricks team NS can win if everyone plays optimally.

The first line has a single integer T, the number of test cases.

Each test case starts with a line containing a string (one of H, S, C, D) representing the trump suit and an integer R representing the number of cards each player is dealt. The next 4 lines each contain a space-separated list of R cards. A card is represented as a string XY, where X is one of A, K, Q, J, T (representing 10), 9, 8, 7, 6, 5, 4, 3, 2, and Y is the suit (one of H, S, C, D). The 4 lines contain the hands of the players N, E, S, and W, in this order. Note that no card appears twice!

Limits

• 1 ≤ T ≤ 100
• 1 ≤ R ≤ 4

For each test case print a single integer, the maximum number of tricks that the NS team can win.

2
S 1
2H
AH
2S
KH
NT 1
2H
AH
2S
KH

1
0