Yeetzhee

Pommel은 집에서 몹시 지루해서 N개의 주사위를 사용하는 새로운 게임을 만들었다. 각 주사위에는 1부터 M까지의 수가 적혀 있다. 주사위를 던질 때마다 M개의 가능한 값 각각이 나올 확률은 동일하다.

Pommel은 모든 주사위를 한 줄로 놓는다. 왼쪽에서 오른쪽으로 주사위를 하나씩 처리한다. 각 주사위를 굴릴 때 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이 이 기댓값을 최소화하도록 최적으로 플레이한다고 할 때, 게임에서 승리할 때까지 필요한 총 주사위 굴림 횟수의 기댓값은 얼마인가?

유효한 모든 입력에서 Pommel이 게임에서 승리하는 것이 가능함이 보장된다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ K ≤ M. 모든 i에 대해 1 ≤ $A_{i}$. $A_{1}$ + $A_{2}$ + ... + $A_{K}$ = N. 모든 i에 대해 $A_{i}$ ≤ $A_{i+1}$.

테스트 세트 1

2 ≤ N ≤ 6. 2 ≤ M ≤ 6.

테스트 세트 2

2 ≤ N ≤ 50. 2 ≤ M ≤ 50.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 N, M, K가 주어진다. 그다음, 최종적으로 만들어야 하는 그룹들을 설명하는 K개의 줄이 주어진다. i번째 줄에는 $A_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작한다)이고, y은 Pommel이 게임에서 승리하기 위해 모든 주사위를 굴리는 데 필요한 횟수의 기댓값이다.

y은 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 인정된다. 이것이 의미하는 바와 허용되는 실수 형식에 관한 설명은 FAQ에서 확인할 수 있다.

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

• Pommel은 첫 번째 주사위를 한 번 던진다.

• Pommel은 두 번째 주사위를 한 번 던진다.

• 첫 번째와 두 번째 주사위의 값이 같다면, Pommel은 세 번째 주사위가 앞의 두 주사위와 다른 값이 나올 때까지 계속 던진다. 평균적으로 1.2번의 주사위 굴림이 필요하다.

• 첫 번째와 두 번째 주사위의 값이 다르다면, Pommel은 세 번째 주사위가 첫 번째 또는 두 번째 주사위와 같은 값이 나올 때까지 계속 던진다. 평균적으로 3번의 주사위 굴림이 필요하다.

이 전략에서 Pommel은 평균적으로 주사위를 4.7번 (1 + 1 + 1/6 × 1.2 + 5/6 × 3) 굴린다.

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

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