비밀번호 문제 (큰 입력)

비밀번호가 아주 길어서 입력하다가 가끔 오타를 낸다. 지금은 비밀번호의 앞부분만 입력한 상태인데, 앞에서 누른 글자 중 몇 개는 엉뚱한 키를 눌렀을 수도 있다. 각 글자를 제대로 눌렀을 확률이 주어졌을 때, 앞으로 어떻게 해야 할까?

선택지는 세 가지다.

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번이면 된다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $A$와 $B$가 주어진다. $A$는 이미 입력한 글자의 개수이고, $B$는 비밀번호 전체의 글자 개수다.

다음 줄에는 $A$개의 실수 $p_1, p_2, \dots, p_A$가 공백으로 구분되어 주어진다. $p_i$는 비밀번호의 $i$번째 글자를 제대로 입력했을 확률이다. 각 실수는 숫자와 소수점 한 개로만 이루어지며, 소수점이 맨 앞이나 맨 뒤에 오는 경우는 없다.

제한

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

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

$y$는 소수점 아래 여섯째 자리까지 반올림해 항상 소수점 아래 여섯 자리로 출력한다.