제인의 꽃집 (Large)

문제

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

제인은 $M$ 개월 기간의 IRR(내부 수익률, Internal Rate of Return)을 계산해서 꽃집이 얼마나 성공할지 예측하려고 한다. (시점, 현금 흐름) 쌍 $(i, C_i)$ 가 주어질 때 IRR은 마지막 달이 끝나는 시점의 현금 총액을 정확히 0으로 만드는 복리 이자율이다. IRR이 높을수록 사업이 성공적이다. IRR이 물가 상승률보다 낮다면 애초에 사업을 시작하지 않는 편이 현명하다.

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

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

이 경우 식을 만족하는 이자율은 약 8.8963% 하나뿐이다. 일반적으로 IRR $r$ 은 다음 식의 해이다.

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

제인의 사업의 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$ ( $0 \le i \le M$ )

출력

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

모든 테스트 케이스에서 정확한 IRR과 가장 가까운 반올림 경계(소수점 아래 12자리로 나타낸 이웃한 두 값의 중점) 사이의 거리는 $10^{-13}$ 보다 크다. 따라서 정확한 IRR과의 오차가 $10^{-13}$ 미만인 값을 반올림하면 기대 출력과 같은 결과를 얻는다.

힌트

예제의 첫 번째 테스트 케이스에서 IRR은 0이다. 제인은 낸 돈을 이자 없이 정확히 돌려받을 뿐이다.