Little Ruins is a studious boy, recently he learned inequation!
As homework, his teacher gives him a problem of inequation: give you an array a with length $N-1$, please find an array $x$ with length $N$ and $x_i \times x_{i+1} \geq a_i$ for each $i$ from $1$ to $N-1$ and try to
minimize the sum of $x$.
First line contains an integer $T$, which indicates the number of test cases.
Every test case begins with an integers $N$, which is the length of array $x$.
The second line contains $N-1$ integers $a_1$, $a_2$, $\cdots$, $a_{N-1}$, indicating the array $a$.
Limits
$1 \leq T \leq 50$.
$1 \leq N \leq 2000$.
$0 < a_i \leq 10^4$.
For 80\% of the use cases, $1 \leq N \leq 100$ holds.
For every test case, you should output
'Case #x: y', where
x indicates the case number and counts from
1 and
y is the result.
Round the
y to the fifth digit after the decimal point.