Jane's Flower Shop (Large)

Jane plans to open a flower shop in the local flower market. The initial cost includes the booth license, furnishings and decorations, a truck to carry flowers from the greenhouse to the shop, and so on. Jane has to recoup these costs from the income she earns. She has estimated the net income she will earn in each of the next $M$ months.

Jane wants to predict how successful her flower shop will be by calculating the IRR (Internal Rate of Return) over the $M$-month period. Given a series of (time, cash flow) pairs $(i, C_i)$, the IRR is the compound interest rate that makes the total cash exactly 0 at the end of the last month. The higher the IRR, the more successful the business. If the IRR is lower than the inflation rate, it would be wise not to start the business at all.

For example, suppose the initial cost is $10,000 and the shop runs for 3 months with net incomes of $3,000, $4,000, and $5,000, in that order. Then the IRR $r$ is given by:

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

In this case exactly one rate, about 8.8963%, satisfies the equation. In general, the IRR $r$ is the solution of:

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

Help Jane calculate the IRR of her business. Every test case guarantees that $-1 < r < 1$ and that there is exactly one solution.

The first line gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line holding a positive integer $M$: the number of months the flower shop will be open. The next line contains $M+1$ non-negative integers $C_0, C_1, \ldots, C_M$. $C_0$ is the initial cost, and all the remaining $C_i$ are profits. The shop always makes either a positive or a zero net profit each month, never a negative one.

Limits

• $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$)

For each test case, output one line of the form Case #x: y, where x is the test case number (starting from 1) and y is the IRR of Jane's business rounded to 12 digits after the decimal point. Print all 12 digits after the decimal point. If the rounded value is zero, print 0.000000000000 without a sign.

In every test case, the exact IRR is more than $10^{-13}$ away from the nearest rounding boundary (the midpoint of two neighboring 12-digit values). So any value within $10^{-13}$ of the exact IRR rounds to the expected output.

In the first sample test case the IRR is 0: Jane only gets back the money she paid, with no interest.