Dou Di Zhu Hand Clearing

Niuniu has recently become addicted to a card game called Dou Di Zhu. The game is played with a deck of 54 cards including the four suits (♠, ♥, ♣, ♦) and two jokers. The cards are ranked (from lowest to highest) as follows: $$3<4<5<6<7<8<9<10<J<Q<K<A<2<\text{Small Joker}<\text{Big Joker}.$$ Note that the suits do not affect the ranking. In each round, a hand consists of n cards. Players take turns playing legal card combinations until one player has no cards left and wins the game.

Niuniu is only interested in knowing, for several hands, the minimum number of plays required to clear his hand. In each play, he is allowed to play one of the following card patterns (which are similar to, but slightly different from, the usual rules):

• Single: Any single card.
• Pair: Two cards of the same rank. (Note: the two jokers cannot form a pair.)
• Triple: Three cards of the same rank.
• Triple with Single: Three cards of the same rank plus one other (different) single card.
• Triple with Pair: Three cards of the same rank plus a pair (of a different rank; again, a pair of jokers is not allowed).
• Bomb: Four cards of the same rank.
• Rocket: The two jokers (Small Joker and Big Joker together).
• Straight: Five or more consecutive cards (by rank) from 3 up to A. (Cards 2 and jokers cannot be used in a straight.) Each card in the straight appears once.
• Pair Sequence: Three or more consecutive pairs (by rank) from 3 up to A. Each rank in the sequence contributes two cards.
• Triple Sequence: Two or more consecutive triples (by rank) from 3 up to A. Each rank in the sequence contributes three cards.
• Four with Two Singles: Four cards of the same rank plus any two other cards (these two cards can be of any rank except the bomb's rank). The two additional cards are selected individually (they may be from the same rank if available).

Your task is to determine, for each hand given, the minimum number of plays required to use up all the cards. It is guaranteed that a solution always exists by playing singles one by one, but you are to minimize the number of plays using any legal combination.

Note: In this problem the two jokers cannot form a pair.

inputFormat

The first line contains a positive integer T (T > 0), the number of test cases.
For each test case, the first line contains an integer n (1 ≤ n ≤ 20), the number of cards in the hand. The second line contains n strings separated by spaces, each representing a card. The cards are one of the following: "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2", "小王" (Small Joker), and "大王" (Big Joker).

outputFormat

For each test case, output a single line with a non-negative integer representing the minimum number of plays required to clear the hand.

sample

1
1
3

1