헤지모니 (작은 입력)

코헨 남작이 가꾸는 울타리는 이 나라에서 가장 보기 좋은 울타리다. 울타리는 일직선으로 나란히 심은 관목 $N$개로 이루어져 있고, 관목에는 왼쪽에서 오른쪽으로 1번부터 $N$번까지 번호가 붙어 있다. 이웃들은 모든 관목의 높이가 같아지도록 자기 울타리를 다듬는다. 코헨 남작의 정원사는 다른 방식으로 일하며, 남작은 이 방식이 해마다 상을 받는 비결이라고 확신한다.

정원사는 2번 관목에서 시작해 오른쪽으로 한 그루씩 옮겨 가며 $N-1$번 관목까지 손질한다. 각 관목에서 정원사는 양옆 두 관목의 높이의 평균을 본다. 관목이 그 평균보다 높으면 윗부분을 잘라 높이를 평균과 정확히 같게 만든다. 이미 평균과 같거나 그보다 낮으면 손대지 않고 넘어간다. 어느 경우든 정원사는 곧바로 오른쪽 다음 관목으로 이동한다.

정원사는 항상 그 시점의 높이를 기준으로 판단하므로, $i$번 관목을 자르면 $i+1$번 관목이 비교할 평균도 달라진다. 1번 관목과 $N$번 관목은 절대 자르지 않는다.

울타리마다 정원사가 손질을 끝낸 뒤 $N-1$번 관목의 높이를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에 정수 $N$이 주어지고, 둘째 줄에 1번부터 $N$번까지 관목의 높이 $N$개가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 100$
• $3 \le N \le 10$
• 각 높이는 1 이상 1000 이하의 정수다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 손질이 끝난 뒤 $N-1$번 관목의 높이다.

$y$는 소수점 아래를 정확히 8자리까지 출력한다. 예를 들어 5.00000000처럼 쓴다. 답은 항상 $1/256$의 정수배라서 8자리로 오차 없이 나타낼 수 있고, 반올림은 일어나지 않는다.