Dou Dizhu Minimal Moves

Dou Dizhu is a popular card game played with a 54‐card deck: the cards from A to K in four suits (♠, ♥, ♣, ♦) plus two jokers (small joker and big joker). The ranking of the cards is defined as follows:

\(3<4<5<6<7<8<9<10<J<Q<K<A<2<\text{small joker}<\text{big joker}\)

In each round, a hand consists of \(n\) cards. A player may play a selection of cards in one move provided they form one of the allowed combinations. The player who manages to play all his/her cards first wins the game.

In this problem, the allowed combinations are similar to standard Dou Dizhu (with slight modifications) and are defined as follows:

• Single: Any one card.
• Pair: Two cards of the same rank.
• Triple: Three cards of the same rank.
• Bomb: Four cards of the same rank.
• Rocket: The combination of the small joker and the big joker.
• Straight: A sequence of at least 5 consecutive cards (by rank) taken from the set \(\{3,4,5,6,7,8,9,10,J,Q,K,A\}\). Note that cards with rank 2 or the jokers cannot be used in a straight.
• Consecutive Pairs: A sequence of at least 3 consecutive ranks (from \(3\) to \(A\)) where each rank contributes a pair (i.e. two cards of the same rank).

Your task is: Given several hands (each hand is one set of cards), determine the minimum number of moves required to play all the cards in that hand.

It is guaranteed that in each hand the cards are from the following set:

3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A, 2, SJ, BJ (where SJ denotes the small joker and BJ denotes the big joker).

inputFormat

The first line contains an integer \(T\) (\(1 \le T \le 20\)), the number of test cases. For each test case:

• The first line contains an integer \(n\) (\(1 \le n \le 20\)), the number of cards in the hand.
• The second line contains \(n\) space-separated strings representing the cards. Each card is one of: 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A, 2, SJ, BJ.

It is guaranteed that the given hand is a valid subset of the 54-card deck.

outputFormat

For each test case output a single line containing an integer — the minimum number of moves required to play all cards in the hand.

sample

4
5
3 4 5 6 7
4
A A A A
6
3 3 4 4 5 5
8
3 3 3 4 4 5 5 6

1
1
1
3