我的密码非常长，有时在输入时会出错。目前我已经输入了密码的一部分，但可能已经犯了一些错误。具体来说，我在输入之前的一个或多个字符时可能按错了键。已知我输入每个字符正确的概率，我该怎么做？

我有三个选项： 1. 继续输入剩余的密码，然后按“回车”。我知道我会完美地输入剩余的字符。如果事实证明之前输入的字符中有错误的，我将不得不重新输入整个密码并再次按“回车”——但我知道第二次我一定会输入正确。 2. 按若干次“退格”键，删除最后输入的若干个字符，然后补全剩余的密码并按“回车”（同选项 1）。如果我没有删除的字符中存在错误，我将不得不重新输入整个密码并按“回车”，我知道第二次我一定会输入正确。 3. 直接按“回车”放弃当前输入，从头开始重新输入密码，并再次按“回车”。我知道这次我一定会输入正确。

我希望最小化所需的期望按键次数。每个字符占用 1 次按键；每次“退格”占用 1 次按键；按“回车”完成尝试或放弃当前尝试均占用 1 次按键。

注意：“期望”按键次数是指在相同情况下重复非常多次后，所需按键次数的平均值。请参考下方的示例。

样例

假设我的密码是 "guest"，我已经输入了前两个字符，但我输入每个字符时有 40% 的概率犯错。那么有四种情况： 我没有出错地输入了 "gu"。这种情况发生的概率为 $0.6 \times 0.6 = 0.36$。 我正确输入了 'g' 但在输入 'u' 时犯了错。此时我仍然输入了两个字母，但第二个是错的："gX"（此处 'X' 代表输错的字母）。这种情况发生的概率为 $0.6 \times 0.4 = 0.24$。 我正确输入了 'u' 但在输入 'g' 时犯了错："Xu"。这种情况发生的概率为 $0.4 \times 0.6 = 0.24$。 我在输入两个字母时都犯了错，所以我有两个错误的字母："XX"。这种情况发生的概率为 $0.4 \times 0.4 = 0.16$。

我不知道自己实际上犯了多少错误，但对于任何策略，我都可以计算出所需的期望按键次数。

对于“继续输入”策略：我有 0.36 的概率需要 4 次按键，有 0.64 的概率需要 10 次按键。如果我重复试验多次，那么 36% 的情况下我会使用 4 次按键，其余 64% 的情况下使用 10 次按键，因此所需的平均按键次数为 $0.36 \times 4 + 0.64 \times 10 = 7.84$。然而在这种情况下，直接按回车更好，这只需要 7 次按键。

输入格式 1

3
2 5
0.6 0.6
1 20
1
3 4
1 0.9 0.1

输出格式 1

Case #1: 7.000000
Case #2: 20.000000
Case #3: 4.500000

输入格式

输入的第一行包含测试用例的数量 T。接下来是 T 个测试用例。每个测试用例的第一行包含两个整数 A 和 B。A 是我已经输入的字符数，B 是密码的总字符数。

随后的一行包含 A 个实数：$p_1, p_2, \dots, p_A$。$p_i$ 表示我正确输入密码中第 $i$ 个字母的概率。这些实数由十进制数字和最多一个小数点组成。小数点不会是数字的第一个或最后一个字符。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 x 是用例编号（从 1 开始），y 是我所需的额外按键次数的期望值（不计入已经输入的字符），并假设我选择了最优策略。y 的误差必须在 $10^{-6}$ 以内。

数据范围

$1 \le T \le 20$。 $0 \le p_i \le 1$（对于所有 $i$）。

子任务 1

$1 \le A \le 3$。 $A < B \le 100$。

子任务 2

$1 \le A \le 99999$。 $A < B \le 100000$。