Password Retyping

My password is very long, so I sometimes mistype it. Right now I have typed only the first part of it, and some of the characters I already typed may be wrong. The screen shows how many characters I have entered but not which ones are wrong. Given the probability that I pressed each of those characters correctly, what should I do next?

I have three options.

1. Type the remaining characters and press enter. Everything I type from now on is correct. If even one of the characters I typed earlier is wrong, this attempt fails, so I have to type the whole password again from the start and press enter once more. The second attempt always succeeds.
2. Press backspace a number of times to delete the characters I typed most recently. After that I finish exactly as in option 1: type the remaining characters and press enter. If even one of the characters I kept is wrong, I again have to type the whole password from the start and press enter, and that attempt always succeeds.
3. Press enter right away to abandon this attempt, then type the whole password from the start and press enter. This attempt always succeeds.

Typing one character counts as 1 keystroke, and backspace and enter each count as 1 keystroke as well. I want the expected number of keystrokes to be as small as possible. The expected number is the average number of keystrokes needed if the same situation is repeated a great many times.

A worked example

Suppose the password is guest, I have already typed the first two characters, and the chance of mistyping each of them was $40\%$. There are four cases.

• gu: both characters are right. The probability is $0.6 \times 0.6 = 0.36$.
• gX: the g is right and the u is wrong. The probability is $0.6 \times 0.4 = 0.24$. Here X stands for a mistyped character.
• Xu: the g is wrong and the u is right. The probability is $0.4 \times 0.6 = 0.24$.
• XX: both characters are wrong. The probability is $0.4 \times 0.4 = 0.16$.

I do not know how many characters I actually got wrong, but I can compute the expected number of keystrokes for each strategy.

If I keep typing, I need 4 keystrokes with probability $0.36$ and 10 keystrokes with probability $0.64$, so the expectation is $0.36 \times 4 + 0.64 \times 10 = 7.84$. In this case pressing enter right away and spending 7 keystrokes is better.

The first line contains the number of test cases $T$.

The first line of each test case contains two integers $A$ and $B$. $A$ is the number of characters I have already typed, and $B$ is the total length of the password. The next line contains $A$ real numbers $p_1, p_2, \ldots, p_A$ separated by spaces. $p_i$ is the probability that I typed the $i$-th character of the password correctly. Each real number consists of digits and at most one decimal point, and the decimal point is never the first or the last character of a number.

Limits

• $1 \le T \le 20$
• $1 \le A \le 3$
• $A < B \le 100$
• $0 \le p_i \le 1$ for every $i$

For each test case, print one line in the form Case #x: y. Here $x$ is the test case number starting from 1, and $y$ is the expected number of further keystrokes when I choose the best strategy. The $A$ characters I have already typed are not counted.

Round $y$ at the sixth decimal place and print all six decimals. For example, write an answer of 7 as 7.000000.