B. The Magician
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
"And now, the curtain rises."
— ????

You are given some special Tarot cards from the Major Arcana, including The Lovers, Death, The Star, The Moon, The Sun, and The World, along with some other playing cards in hand. You have at most one of each kind of Tarot card, and each Tarot card has a unique ability that can alter the suits of other playing cards in your hand. Your task is to determine the maximum number of flushes that can be played by the playing cards in hand after using the given Tarot cards each at most once.

The playing cards are standard playing cards, shown as below.

Here is a list of Tarot cards abilities.

  • The Star: Converts up to 3 selected playing cards to Diamonds ($$$\diamondsuit$$$).
  • The Moon: Converts up to 3 selected playing cards to Clubs ($$$\clubsuit$$$).
  • The Sun: Converts up to 3 selected playing cards to Hearts ($$$\heartsuit$$$).
  • The World: Converts up to 3 selected playing cards to Spades ($$$\spadesuit$$$).
  • The Lovers: Converts 1 selected playing card into a Wild Card ($$$\circledast$$$, can be used as any suit).
  • Death: Select exactly 2 playing cards, replace one card with the copy of the other card (copy the suit, the rank, and the Wild Card status).

You can use the Tarot cards in any order. Each given Tarot card can be used at most once and can never be used at all. There is a special rule about The Lovers:

  • Once a playing card has been converted into a Wild Card (using The Lovers or Death), it remains a Wild Card even after applying The Star, The Moon, The Sun, and The World;
  • However, if Death is used to replace a Wild Card with a copy of another card that is not a Wild Card, the resulting card will not be a Wild Card.

A flush is a set of $$$5$$$ playing cards, which could be considered a same suit: there is a suit (among Diamond, Club, Heart, and Spade) such that each of the $$$5$$$ playing cards is either of this suit or is a Wild Card.

Playing a flush means that the $$$5$$$ cards forming the flush are discarded from hand, all of which cannot be used in another flush. To the contrary of many card games including Balatro, you draw no new cards from the deck after playing cards.

Input

The input consists of multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 13$$$) — the number of test cases. The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 52$$$), the number of playing cards in hand.

The second line contains $$$n$$$ space-separated strings, each representing a playing card in hand. Each playing card is represented by two characters: one for rank and one for suit, where the suit is one of D (Diamonds), C (Clubs), H (Hearts), or S (Spades), and the rank is one of 2-9, T (10, Ten), J (Jack), Q (Queen), K (King), or A (Ace).

The third line contains six space-separated integers $$$t_1, t_2, t_3, t_4, t_5, t_6 ~ (0 \leq t_i \leq 1)$$$, where:

  • $$$t_1$$$ represents the number of The Star.
  • $$$t_2$$$ represents the number of The Moon.
  • $$$t_3$$$ represents the number of The Sun.
  • $$$t_4$$$ represents the number of The World.
  • $$$t_5$$$ represents the number of The Lovers.
  • $$$t_6$$$ represents the number of Death.

It is guaranteed that the sum of $$$n$$$ among $$$T$$$ test cases does not exceed $$$104 = 52 \times 2$$$, and the playing cards are pairwise distinct in each test case.

Output

For each test case, print the maximum number of flushes that can be played in a single line.

Example
Input
4
5
2H 3H 4H 5H 6D
1 1 1 1 0 0
5
2S 3S 4D 5C 6D
0 0 1 0 1 1
5
2S 3S 4D 5C 6D
0 0 1 0 1 0
13
AS 2S 3S 4S 5H 6H 7H 8H 9H TH JH QH KH
0 0 0 0 0 1
Output
1
1
0
2
Note

In the first case, we can convert $$$6 \diamondsuit$$$ into $$$6 \heartsuit$$$ using The Sun, and play $$$2 \heartsuit 3 \heartsuit 4 \heartsuit 5 \heartsuit 6 \heartsuit $$$ as a flush. This is not the only possible way; another possible way to play the same set of cards is:

  • Convert $$$4 \heartsuit 5 \heartsuit 6 \diamondsuit$$$ into $$$4 \spadesuit 5 \spadesuit 6 \spadesuit$$$ using The World;
  • Convert $$$4 \spadesuit 5 \spadesuit 6 \spadesuit$$$ into $$$4 \heartsuit 5 \heartsuit 6 \heartsuit$$$ using The Sun.

In the second test case, one possible way to play a flush is:

  • Convert $$$2 \spadesuit 3 \spadesuit 4 \diamondsuit$$$ into $$$2 \heartsuit 3 \heartsuit 4 \heartsuit$$$ using The Sun;
  • Convert $$$5 \clubsuit$$$ into $$$5{\circledast}$$$ using The Lovers;
  • Replace $$$6 \diamondsuit$$$ with a copy of $$$5{\circledast}$$$ using Death;
  • Play $$$2 \heartsuit 3 \heartsuit 4 \heartsuit 5{\circledast} 5{\circledast}$$$.