Problem Description

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$.

Input

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.

Output

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.

2
4
2 3 2
4
1 2 3

Case #1: 5.77350
Case #2: 5.47723