비밀번호 다시 입력하기

비밀번호가 아주 길어서 입력하다 보면 가끔 오타가 난다. 지금은 비밀번호의 앞부분만 입력한 상태인데, 이미 친 글자 가운데 일부가 틀렸을 수도 있다. 화면에는 몇 글자를 입력했는지만 보이므로 어디를 틀렸는지는 알 수 없다. 각 글자를 제대로 눌렀을 확률이 주어질 때, 지금부터 무엇을 해야 하는가?

선택지는 세 가지다.

1. 남은 글자를 끝까지 입력하고 엔터를 누른다. 지금부터 치는 글자는 절대 틀리지 않는다. 앞에서 친 글자 중 하나라도 틀렸다면 이번 시도는 실패하므로 비밀번호를 처음부터 전부 다시 입력하고 엔터를 한 번 더 눌러야 하며, 두 번째 시도는 반드시 성공한다.
2. 백스페이스를 몇 번 눌러 마지막에 친 글자를 지운다. 그다음에는 1번과 똑같이 남은 글자를 모두 입력하고 엔터를 누른다. 지우지 않고 남겨 둔 글자 중 하나라도 틀렸다면 역시 처음부터 다시 입력하고 엔터를 눌러야 하며, 이때도 반드시 성공한다.
3. 곧바로 엔터를 눌러 이번 시도를 포기한 뒤, 비밀번호를 처음부터 전부 입력하고 엔터를 누른다. 이 시도는 반드시 성공한다.

글자 하나를 입력하면 키를 1번 누른 것으로 세고, 백스페이스와 엔터도 각각 1번으로 센다. 키를 누르는 횟수의 기댓값을 가장 작게 만들고 싶다. 기댓값은 같은 상황이 아주 여러 번 반복될 때 필요한 키 입력 횟수의 평균이다.

계산 예

비밀번호가 guest이고 앞의 두 글자를 이미 쳤는데, 두 글자 각각을 틀리게 누를 확률이 $40\%$였다고 하자. 경우는 네 가지다.

• gu: 둘 다 맞게 쳤다. 확률은 $0.6 \times 0.6 = 0.36$이다.
• gX: g는 맞고 u는 틀렸다. 확률은 $0.6 \times 0.4 = 0.24$이다. 여기서 X는 잘못 눌린 글자를 뜻한다.
• Xu: g는 틀리고 u는 맞다. 확률은 $0.4 \times 0.6 = 0.24$이다.
• XX: 둘 다 틀렸다. 확률은 $0.4 \times 0.4 = 0.16$이다.

실제로 몇 글자를 틀렸는지는 알 수 없지만, 전략마다 키 입력 횟수의 기댓값은 계산할 수 있다.

그대로 계속 입력하면 $0.36$의 확률로 4번, $0.64$의 확률로 10번 키를 누르므로 기댓값은 $0.36 \times 4 + 0.64 \times 10 = 7.84$다. 이 경우에는 바로 엔터를 눌러 7번에 끝내는 쪽이 더 낫다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $A$와 $B$가 주어진다. $A$는 이미 입력한 글자 수이고, $B$는 비밀번호 전체의 길이다. 다음 줄에는 $A$개의 실수 $p_1, p_2, \ldots, p_A$가 공백으로 구분되어 주어진다. $p_i$는 비밀번호의 $i$번째 글자를 제대로 입력했을 확률이다. 각 실수는 숫자와 소수점 하나로만 이루어지며, 소수점이 맨 앞이나 맨 뒤에 오지는 않는다.

제한

• $1 \le T \le 20$
• $1 \le A \le 3$
• $A < B \le 100$
• 모든 $i$에 대해 $0 \le p_i \le 1$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 최적의 전략을 골랐을 때 앞으로 더 눌러야 하는 키 입력 횟수의 기댓값이다. 이미 입력한 $A$개의 글자는 세지 않는다.

$y$는 소수점 아래 여섯째 자리에서 반올림해 소수점 아래 여섯 자리를 빠짐없이 적는다. 예를 들어 답이 7이면 7.000000으로 쓴다.