몬스터 경로 (라지)

코드자몬은 몬스터 조련사가 현실 세계를 돌아다니며 몬스터를 잡는 모바일 게임이다. 당신이 쓰는 휴대폰은 낡아서 배터리가 금방 닳는다. 몬스터를 최대한 많이 잡으려면 이동 경로를 신중하게 골라야 한다.

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

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

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

$R = 1$이고 $C = 1$이면 이동할 수 있는 칸이 하나도 없다. 이때는 $S$가 $1$ 이상이어도 기댓값이 $0$이다.

첫 줄에 테스트 케이스의 수 $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 20$
• $1 \le C \le 20$
• $0 \le R_s < R$
• $0 \le C_s < C$
• $0 \le Q < P \le 1$
• $0 \le S \le 9$

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

$y$는 소수점 아래 여덟째 자리에서 반올림해 소수점 아래 자릿수가 정확히 일곱 개가 되도록 출력한다. 값이 정수여도 2.0000000처럼 일곱 자리를 모두 적는다. 반올림 결과가 갈리는 입력, 즉 정답이 반올림 경계에 정확히 걸리는 입력은 주어지지 않는다.

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

같은 예제의 두 번째 테스트 케이스에서 최적 경로 하나는 $(9,1) \to (9,2) \to (8,2) \to (8,3) \to (8,2)$이다. 기댓값은 $0.1 + 0.6121 + 0.1 + 0.23743359 = 1.04953359$이고, 출력 형식에 맞춰 반올림하면 $1.0495336$이다. 마지막 항 $0.23743359$는 $(8,2)$에 두 번째로 들어갈 때 그 칸에 몬스터가 아직 남아 있을 확률 $1 - 0.6121$에 잡을 확률 $0.6121$을 곱한 값이다.