Migrated from Lutece 1502 I

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

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}\ge 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$ ($1\le T\le 50$), which indicates the number of test cases.

Every test case begins with an integers $N$ ($1\le N\le 2000$), which is the length of array $x$.

The second line contains $N-1$ integers $a_1, a_2, \ldots , a_{N-1}$ ($0<a_i\le 10^4$), indicating the array $a$.

For $80\%$ of the use cases, $1\le N\le 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.

Samples

2
4
2 3 2
4
1 2 3

Case #1: 5.77350
Case #2: 5.47723

Resources

第二届中国大学生程序设计竞赛 杭州站（CCPC 2016 Hangzhou Site）