카드 합치기

Panko는 N장의 카드를 한 줄로 늘어놓고 게임을 한다. i번째 카드에는 정수 $A_{i}$가 적혀 있다.

게임은 N - 1개의 라운드에 걸쳐 진행된다. 각 라운드에서 Panko는 서로 인접한 카드 한 쌍을 골라 합친다. 두 카드에 정수 X와 Y가 적혀 있다고 하자. 두 카드를 합치기 위해 Panko는 X + Y가 적힌 새 카드를 만든다. 그런 다음 원래의 두 카드를 줄에서 제거하고, 그 카드들이 있던 자리에 새 카드를 놓는다. 마지막으로 Panko는 이 합치기로 X + Y점을 얻는다. 각 라운드에서 Panko는 현재 존재하는 모든 인접한 카드 쌍의 집합 중 한 쌍을 균등한 확률로 무작위 선택한다.

N - 1개의 라운드가 모두 끝난 뒤, Panko의 총점은 각 합치기에서 얻은 점수의 합이다. 게임이 끝났을 때 Panko의 총점의 기댓값은 얼마인가?

제한

시간 제한: 40초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 모든 i에 대해 1 ≤ $A_{i}$ ≤ $10^{9}$.

테스트 세트 1

2 ≤ N ≤ 9.

테스트 세트 2

2 ≤ N ≤ 100.

테스트 세트 3

2 ≤ N ≤ 5000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N이 포함된 한 줄로 시작한다. 이어지는 두 번째 줄에는 초기 카드 줄을 나타내는 N개의 정수가 주어진다. i번째 정수는 $A_{i}$이다.

각 테스트 케이스마다 Case #x: y이 포함된 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 게임이 끝났을 때의 총점의 기댓값이다.

y이 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 의미하는 바와 허용되는 실수 형식에 대한 설명은 FAQ을 참고하라.

예제 케이스 #1에서 N = 3이다. 초기 카드 줄은 [2, 1, 10]이다. 첫 번째 라운드에서 Panko에게는 두 가지 선택지가 있으며, 그중 하나를 무작위로 선택한다.

• Panko가 첫 번째 쌍 (2, 1)을 합치면 카드 줄은 [3, 10]이 되고, 총점에 2 + 1 = 3점이 더해진다. 두 번째 라운드에는 단 하나의 쌍 (3, 10)만 남는다. 이 카드들을 합치면 카드 줄은 [13]이 되고, 총점에 3 + 10 = 13점이 더해진다. Panko는 3 + 13 = 16점으로 게임을 마친다.

• Panko가 두 번째 쌍 (1, 10)을 합치면 카드 줄은 [2, 11]이 되고, 총점에 1 + 10 = 11점이 더해진다. 두 번째 라운드에는 단 하나의 쌍 (2, 11)만 남는다. 이 카드들을 합치면 카드 줄은 [13]이 되고, 총점에 2 + 11 = 13점이 더해진다. Panko는 11 + 13 = 24점으로 게임을 마친다.

따라서 Panko가 게임을 마칠 때 얻는 점수의 기댓값은 (16 + 24)/2 = 20이다.

예제 케이스 #2에서 N = 5이다. 초기 카드 줄은 [19, 3, 78, 2, 31]이다. 가능한 경우가 너무 많아 모두 나열할 수 없으므로, 여기서는 가능한 게임 하나만 살펴본다:

• 첫 번째 라운드에서 Panko가 쌍 (78, 2)을 합치면 카드 줄은 [19, 3, 80, 31]이 되고, 점수에 78 + 2 = 80이 더해진다.

• 두 번째 라운드에서 Panko가 쌍 (80, 31)을 합치면 카드 줄은 [19, 3, 111]이 되고, 점수에 80 + 31 = 111이 더해진다.

• 세 번째 라운드에서 Panko가 쌍 (19, 3)을 합치면 카드 줄은 [22, 111]이 되고, 점수에 19 + 3 = 22이 더해진다.

• 네 번째 라운드에서 Panko가 쌍 (22, 111)을 합치면 카드 줄은 [133]이 되고, 점수에 22 + 111 = 133이 더해진다.

위에서 설명한 게임이 끝났을 때 Panko의 총점은 80 + 111 + 22 + 133 = 346이다.