몬스터 경로 (스몰)

코드자몬(Codejamon)은 몬스터 조련사가 현실 세계를 돌아다니며 몬스터를 잡는 모바일 게임이다. 배터리가 얼마 남지 않은 낡은 스마트폰을 쓰고 있으므로, 몬스터를 최대한 많이 잡으려면 이동 경로를 신중하게 골라야 한다.

코드자몬 세계는 $R$행 $C$열짜리 직사각형 격자다. 행 번호는 위에서 아래로 0부터, 열 번호는 왼쪽에서 오른쪽으로 0부터 매긴다. 출발 칸은 $R_s$행 $C_s$열이고, 여기서 정확히 $S$번 이동한다. 한 번의 이동으로는 지금 있는 칸과 변을 맞댄 칸으로만 갈 수 있다. 꼭짓점만 맞댄 칸으로는 갈 수 없다.

아직 몬스터를 잡지 못한 칸으로 들어가면, 그 칸에 몬스터 유인기가 있으면 확률 $P$로, 없으면 확률 $Q$로 그 칸의 몬스터를 잡는다. 어떤 칸에서 몬스터를 잡으면 그 몬스터는 사라지고, 나중에 그 칸에 다시 들어가도 더 잡을 몬스터가 없다. 잡지 못했다면 나중에 그 칸에 들어갈 때마다 다시 시도한다. 출발 칸은 예외다. 첫 이동을 하기 전에는 출발 칸에서 몬스터를 잡을 기회가 없다.

움직이기 전에 경로 전체를 최적으로 계획한다고 할 때, 잡는 몬스터 수의 기댓값이 최대 얼마인지 구하라.

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

각 테스트 케이스의 첫째 줄에는 정수 다섯 개 $R$, $C$, $R_s$, $C_s$, $S$가 주어진다. $R$과 $C$는 격자의 행 개수와 열 개수이고, ($R_s$, $C_s$)는 출발 칸의 행과 열이며, $S$는 이동 횟수다.

다음 줄에는 소수 $P$와 $Q$가 주어진다. $P$는 유인기가 있는 칸에서 몬스터를 잡을 확률, $Q$는 유인기가 없는 칸에서 몬스터를 잡을 확률이고, 둘 다 소수점 아래 넷째 자리까지 정확히 주어진다.

다음 $R$개 줄에는 각각 문자 $C$개가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 문자는 $i$행 $j$열 칸을 나타내며, .이면 유인기가 없는 칸, A이면 유인기가 있는 칸이다.

제한

• $1 \le T \le 100$
• $1 \le R \le 10$
• $1 \le C \le 10$
• $0 \le R_s < R$
• $0 \le C_s < C$
• $0 \le Q < P \le 1$
• $0 \le S \le 5$
• $R = 1$이고 $C = 1$이면 $S = 0$이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 주어진 이동 횟수 안에 잡는 몬스터 수의 기댓값의 최댓값이다.

$y$는 소수점 아래 여덟째 자리에서 반올림해 소수점 아래 자릿수가 정확히 일곱 개가 되도록 출력한다. 여덟째 자리 숫자가 5이면 일곱째 자리를 올린다. 답이 0이면 0.0000000으로 출력한다.

예제의 첫 번째 테스트 케이스에서 최적 경로 중 하나는 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,3)이다. 이 경로에서 잡는 몬스터 수의 기댓값은 0.2 + 0.2 + 0.2 + 0.8 + 0.2 = 1.6이다. 첫 이동 전에는 몬스터를 잡을 기회가 없으므로 확률을 여섯 개가 아니라 다섯 개만 더한다.

두 번째 테스트 케이스에서 최적 경로 중 하나는 (9,1) -> (9,2) -> (8,2) -> (8,3) -> (8,2)이다. 기댓값은 0.1 + 0.6121 + 0.1 + 0.23743359 = 1.04953359이고, 소수점 아래 일곱째 자리까지 맞추면 1.0495336이 된다. (8,2)에 두 번째로 들어갈 때의 0.23743359는 첫 방문에서 실패할 확률 0.3879에 0.6121을 곱한 값이다.