Problem J - Videopoker

Time limit: 15 seconds

Videopoker is the slot machine variant of the currently immensely popular game of poker. It is a variant on draw poker. In this game the player gets a hand consisting of five cards randomly drawn from a standard 52-card deck. From this hand, the player may discard any number of cards (between 0 and 5, inclusive), and change them for new cards randomly drawn from the remainder of the deck. After that, the hand is evaluated and the player is rewarded according to a payout structure. A common payout structure is as follows:

Once you know the payout structure, you can determine for a given hand which cards you must change to maximize your expected reward. We'd like to know this expected reward, given a hand.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

• One line with nine integers x_i (0 ≤ x_i ≤ 1000$) describing the payout structure. The numbers are in increasing order and describe the payout for one pair, two pair, etc, until the royal flush.
• One line with one integer n (1 ≤ n ≤ 10): the number of starting hands to follow.
• n lines, each describing a starting hand. A hand consists of five space separated tokens of the form Xs, with X being the rank (`2' \dots `9', `T', `J', `Q', `K' or `A') and s being the suit (`c', `d', `h' or `s').

Output

Per testcase:

• One line for each starting hand with a floating point number that is the maximal expected reward for that hand. These numbers must have an absolute or relative error less than 10^-6.

1
1 2 3 4 5 10 25 100 250
5
Ah Ac Ad As 2s
Ks Qs Js Ts 2h
Ks Qs 2d 2h 3s
2d 4h 5d 3c 9c
2h 3h 6d 8h Tc

25.000000
8.9574468
1.5467160
0.9361702
0.6608135