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.