Yeetzhee

Pommel은 집에서 매우 심심했기 때문에 $N$개의 주사위를 사용하는 새 게임을 만들었다. 각 주사위에는 1부터 $M$까지의 수가 적혀 있다. 주사위를 던지면 $M$개의 값 각각이 나올 확률이 같다.

Pommel은 모든 주사위를 한 줄로 늘어놓는다. 왼쪽부터 주사위를 하나씩 처리한다. 각 주사위를 굴린 뒤 Pommel은 나온 값을 유지하고 다음 주사위로 넘어가거나 주사위를 다시 굴릴 수 있다. 다음 주사위로 넘어가기 전까지 주사위를 원하는 만큼 다시 굴릴 수 있다.

Pommel이 모든 주사위를 처리하면 게임이 끝난다. 이겼는지 판정하기 위해 주사위를 그룹으로 나눈다. 같은 값이 나온 주사위는 모두 같은 그룹에 들어간다. 따라서 게임을 마쳤을 때 서로 다른 값이 $x$개라면 그룹도 $x$개가 된다. 그런 다음 주사위 그룹을 주사위 개수가 작아지지 않는 순서로 정렬한다.

예를 들어:

• 최종 주사위 결과가 [2, 2, 3, 2, 2, 3]이면 주사위는 두 그룹으로 나뉘고 [3, 3], [2, 2, 2, 2] 순서로 정렬된다.
• 최종 주사위 결과가 [1, 6, 7, 7]이면 주사위는 세 그룹으로 나뉘고 [6], [1], [7, 7] 순서로 정렬된다 (또는 마찬가지로 [1], [6], [7, 7]).

Pommel은 게임을 정확히 $K$개의 그룹으로 끝내고 모든 $i$에 대해 $i$번째 그룹에 정확히 $A_i$개의 주사위가 있으면 이긴다.

이 기댓값을 최소화하도록 Pommel이 최선으로 플레이한다고 가정할 때, 게임에서 이기기까지 필요한 총 주사위 굴림 횟수의 기댓값은 얼마인가?

모든 유효한 입력에 대해 Pommel이 게임에서 이길 수 있음이 보장된다.

입력의 첫 줄에 테스트 케이스 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$, $M$, $K$가 주어진다. 다음 $K$개 줄에는 Pommel이 게임을 마칠 때 만들어야 하는 그룹을 설명하는 값이 주어진다. $i$번째 줄에는 $A_i$가 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 Pommel이 게임에서 이기기까지 주사위를 굴리는 총 횟수의 기댓값이다.

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

• $1 \le T \le 100$.
• $1 \le K \le M$.
• 모든 $i$에 대해 $1 \le A_i$.
• $A_1 + A_2 + \cdots + A_K = N$.
• 모든 $i$에 대해 $A_i \le A_{i+1}$.

예제 1에서 Pommel에게는 $N=3$개의 주사위가 있고, 각 주사위에는 1부터 $M=6$까지의 수가 적혀 있다. 이기려면 Pommel은 $K=2$개의 그룹으로 게임을 마쳐야 한다. 한 그룹에는 주사위가 하나 있어야 하고($A_1=1$), 다른 그룹에는 주사위가 두 개 있어야 한다($A_2=2$). Pommel이 택할 수 있는 최적 전략 중 하나는 다음과 같다.

• Pommel은 첫 번째 주사위를 한 번 던진다.
• Pommel은 두 번째 주사위를 한 번 던진다.
• 첫 번째와 두 번째 주사위의 값이 같으면, Pommel은 세 번째 주사위가 앞의 두 주사위와 다른 값이 나올 때까지 계속 던진다. 평균적으로 주사위를 1.2회 굴린다.
• 첫 번째와 두 번째 주사위의 값이 다르면, Pommel은 세 번째 주사위가 첫 번째 또는 두 번째 주사위의 값과 같아질 때까지 계속 던진다. 평균적으로 주사위를 3회 굴린다.

이 전략으로 Pommel은 평균적으로 주사위를 4.7회 굴린다($1 + 1 + \frac{1}{6} \times 1.2 + \frac{5}{6} \times 3$).

예제 2에서 Pommel에게는 $N=5$개의 주사위가 있고, 각 주사위에는 1부터 $M=2$까지의 수가 적혀 있다. 이기려면 Pommel은 $K=1$개의 그룹으로 게임을 마쳐야 하며, 모든 $N$개의 주사위가 그 그룹에 들어가야 한다($A_1=N$). Pommel은 첫 번째 주사위를 한 번 굴린다. 그런 다음 남은 주사위마다 첫 번째 주사위와 같은 값이 나올 때까지 계속 굴린다. 평균적으로 주사위를 2회 굴린다.

이 전략으로 Pommel은 평균적으로 주사위를 9회 굴린다($1 + 2 + 2 + 2 + 2$).