제인의 꽃집 (Small)

제인은 동네 꽃 시장에 꽃집을 열 계획이다. 초기 비용에는 부스 허가비, 가구와 장식, 온실에서 가게까지 꽃을 실어 나를 트럭 등이 들어간다. 제인은 앞으로 벌어들일 수입으로 이 비용을 회수해야 한다. 제인은 앞으로 $M$개월 동안 매달 얻을 순수입을 미리 추정해 두었다.

제인은 $M$개월 동안의 IRR(내부 수익률, Internal Rate of Return)을 계산해서 꽃집이 얼마나 성공할지 예측하려고 한다. (시각, 현금 흐름) 쌍 $(i, C_i)$가 주어질 때 IRR은 마지막 달이 끝나는 시점에 총 현금을 정확히 0으로 만드는 복리 이자율이다. 즉 IRR $r$은 다음 식을 만족한다.

$-C_0 \cdot (1+r)^M + \sum_{i=1}^{M} C_i \cdot (1+r)^{M-i} = 0$

IRR이 높을수록 사업이 성공적이다. IRR이 물가 상승률보다 낮다면 애초에 사업을 시작하지 않는 편이 현명하다.

예를 들어 초기 비용이 $10,000이고 가게를 3개월 동안 운영하며 매달 순수입이 차례로 $3,000, $4,000, $5,000이라면 IRR $r$은 다음 식으로 구한다.

$-10000 \cdot (1+r)^3 + 3000 \cdot (1+r)^2 + 4000 \cdot (1+r) + 5000 = 0$

이 경우 식을 만족하는 값은 약 8.8963%($r \approx 0.088963$) 하나뿐이다.

제인의 사업의 IRR을 계산해 주자. $-1 < r < 1$이고 각 테스트 케이스마다 해가 정확히 하나 있음이 보장된다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 꽃집을 운영하는 개월 수 $M$이 양의 정수로 주어진다. 다음 줄에는 음이 아닌 정수 $M+1$개 $C_0, C_1, \ldots, C_M$이 주어진다. $C_0$은 초기 비용이고 나머지 $C_i$는 모두 수익이다. 가게는 매달 양수 또는 0의 순이익을 내며 순이익이 음수인 달은 없다.

제한

• $1 \le T \le 100$
• $1 \le M \le 100$
• $C_0 > 0$
• $0 \le C_i \le 1\,000\,000\,000$
• 위 식을 만족하는 $r$은 $-1 < r < 1$ 범위에 정확히 하나 있다.

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고 y는 제인의 사업의 IRR을 소수점 아래 정확히 12자리로 반올림한 값이다. 반올림한 값이 0이면 부호 없이 0.000000000000을 출력한다.

정확한 IRR이 반올림 경계에서 $10^{-14}$ 이내에 있는 입력은 주어지지 않는다.

첫 번째 예제에서 IRR은 0이다. 제인은 들인 돈을 이자 없이 딱 맞게 돌려받았다.