신의 가호를 받은 블랙잭

jtw7913는 DOJ 카지노에서 레이팅을 걸고 블랙잭을 하고 있다. 그는 딜러의 비공개 카드를 포함한 초기 카드와 현재 덱에 남아 있는 카드를 모두 알고 있다.

게임은 조커를 제외한 표준 트럼프 카드 한 벌로 진행한다. 각 카드는 랭크와 문양을 이어 붙인 두 글자의 문자열로 나타낸다. 랭크는 A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K 중 하나이며, 문양은 S, H, D, C 중 하나이다. 예를 들어 AS는 스페이드 에이스이고, TH는 하트 10이다.

카드의 점수는 다음과 같다.

• 2부터 9까지는 적힌 숫자와 같은 점수를 가진다.
• T, J, Q, K는 모두 10점이다.
• 에이스 A는 1점 또는 11점으로 계산할 수 있다.

에이스가 한 장 이상 있는 패에서는 가능한 점수 중 21을 넘지 않는 가장 큰 값을 사용한다. 모든 가능한 점수가 21을 초과한다면 그중 가장 작은 값을 사용한다. 문양은 점수와 승패에 영향을 주지 않는다.

jtw7913와 딜러는 처음에 각각 두 장의 카드를 가지고 시작한다. 처음 받은 두 장만으로 점수가 정확히 21인 경우를 블랙잭이라고 한다. 세 장 이상의 카드로 점수 21을 만든 경우는 블랙잭이 아니다.

게임 시작 직후 양쪽의 블랙잭 여부를 확인한다.

• 둘 다 블랙잭이면 무승부이다.
• jtw7913만 블랙잭이면 jtw7913의 블랙잭 승리이다.
• 딜러만 블랙잭이면 jtw7913의 패배이다.
• 어느 쪽도 블랙잭이 아니면 게임을 계속한다.

게임이 계속되면 jtw7913는 자신의 차례마다 Hit 또는 Stay 중 하나를 선택한다.

• Hit: 덱에 남아 있는 카드 중 한 장을 균등한 확률로 뽑아 자신의 패에 추가한다.
• Stay: 더 이상 카드를 받지 않고 자신의 차례를 끝낸다.

같은 랭크의 카드가 여러 장 남아 있더라도 각각은 서로 다른 실제 카드이다. 따라서 특정 랭크를 뽑을 확률은 남은 카드 중 그 랭크의 카드 수에 비례한다.

jtw7913가 카드를 추가한 직후 점수가 21을 초과하면 즉시 버스트되어 패배한다. 점수가 정확히 21이 되면 자동으로 Stay한다. 덱에 카드가 남아 있지 않으면 Hit할 수 없으며 자동으로 Stay한다.

jtw7913가 Stay한 뒤에는 딜러가 행동한다. 딜러는 현재 점수가 16 이하이면 반드시 Hit하고, 17 이상이면 반드시 Stay한다. 에이스를 11점으로 계산한 소프트 17에서도 Stay한다. 딜러가 Hit하면 남은 카드 중 한 장을 균등한 확률로 뽑는다. 카드를 추가한 뒤 점수가 21을 초과하면 버스트된다. 딜러가 Hit해야 하지만 덱이 비어 있으면 자동으로 Stay한다.

행동이 모두 끝나면 다음과 같이 승패를 정한다.

• jtw7913가 버스트되면 패배한다.
• jtw7913가 버스트되지 않았고 딜러가 버스트되면 승리한다.
• 둘 다 버스트되지 않았다면 점수가 높은 쪽이 승리한다.
• 두 점수가 같으면 무승부이다.

베팅한 레이팅의 양을 $R$이라 하자. 게임 종료 후 jtw7913의 순손익은 일반 승리 시 $+R$, 블랙잭 승리 시 $+1.5R$, 무승부 시 $0$, 패배 시 $-R$이다. 스플릿, 더블 다운, 서렌더, 보험은 사용할 수 없다.

jtw7913는 알고 있는 모든 정보를 이용하여 매 순간 순손익의 기댓값을 최대화하는 행동을 선택한다. 최적으로 행동할 때의 순손익 기댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$R\ N$ $P_1\ P_2$ $D_1\ D_2$ $C_1\ C_2\ \cdots\ C_N$

$P_1,P_2$는 jtw7913의 초기 카드이고, $D_1,D_2$는 딜러의 초기 카드이다. $C_1,C_2,\cdots,C_N$은 현재 덱에 남아 있는 카드이다.

각 테스트 케이스마다 한 줄에 jtw7913가 최적으로 행동할 때 얻는 순손익의 기댓값을 출력한다.

정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정한다.

• $1 \leq T \leq 1\,000$.
• $1 \leq R \leq 4\,009$.
• $1 \leq N \leq 12$.
• 각 카드는 표준 52장 트럼프 카드 중 하나를 나타내는 유효한 두 글자 문자열이다.
• 한 테스트 케이스 안에서 $P_1,P_2,D_1,D_2,C_1,C_2,\cdots,C_N$은 모두 서로 다른 실제 카드이다.
• 모든 테스트 케이스에 대해 $\displaystyle \sum 3^N \leq 600\,000$.