Codejamon 是一款手机游戏，怪物训练师在现实世界中四处走动以捕捉怪物。

你有一个电池寿命很短的旧智能手机，所以你需要仔细选择你的路径来捕捉尽可能多的怪物。

假设 Codejamon 世界是一个 $R$ 行 $C$ 列的矩形网格，行从上到下从 $0$ 开始编号;列从左到右从 $0$ 开始编号。

你在开始时位于单元格 $(R\_s,C\_s)$ 内，已知每个单元格中都藏有一个怪物。

你一共可以移动 $S$ 步，每步都可以从当前单元格走到与当前单元格具有公共边的相邻单元格中。

每当你走到一个怪物尚未被捕获的单元格中时，如果单元格内有怪物吸引子，那么你成功捕获该单元格中的怪物的概率为 $P$，否则为 $Q$。

如果你抓到了某个单元格中的怪物，那么它就会消失，并且该单元格未来不会刷新出新的怪物。

如果你走到某个单元格处时，没有成功抓到位于该单元格的怪物，那么将来再次进入该单元格时，你仍有机会抓到它。

起始单元格是特殊的：在你迈出第一步之前，你没有机会抓住那里的怪物。

如果你以最佳方式计划你的行进路径，那么你能够捕获到的怪物数量的最大可能期望值是多少？

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含五个整数 $R, C, R\_s, C\_s, S$，意义如题目描述所示。

第二行包含两个小数 $P$ 和 $Q$，均保留四位小数。

接下来 $R$ 行，每行包含 $C$ 个用空格隔开的字符，其中第 $i$ 行第 $j$ 列的字符表示第 $i$ 行第 $j$ 列的单元格，如果字符为 .，则表示单元格内没有怪物吸引子，如果字符为 A，则表示单元格内含有怪物吸引子。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 $x$ 是组别编号（从 $1$ 开始），$y$ 是玩家能获得的怪物数量的最大可能期望值。

如果 $y$ 在正确答案的 $10^{-6}$ 的绝对或相对误差范围内，则 $y$ 将被认为是正确的。

数据范围

$1 \le T \le 100$,

$0 \le R\_s < R$,

$0 \le C\_s < C$,

$0 \le Q < P \le 1$

$1 \le R,C \le 20$,

$0 \le S \le 9$

样例解释

在样例＃1中，最佳路径之一是 $(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$。

请记住，在迈出第一步之前没有机会抓住初始格子的怪物。

在样例＃2中，最佳路径之一是 $(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.04953359$）的 $10^{-6}$ 的绝对或相对误差范围内的结果，因此 $1.0495336$ 视为正确。

样例

2
4 4 0 0 5
0.8000 0.2000
. . . .
. . . .
. . A .
. A . A
10 10 9 1 4
0.6121 0.1000
. . A A . . . . . .
A . . . . . . . . .
. . A . . . . A . .
. . . A A . . . . .
. A A A . . . . . A
A . A A . . . . A .
. A . . . . . A . .
. . . . A A . . . .
. . A . . . A . . A
. . . . A . . A . .

Case #1: 1.6000000
Case #2: 1.0495336