U180518 找金币

锣鼓（没错）的服务器爆炸了！由于没有钱维修，你作为三好员工，只能去收集钱了。

你打算挑战大名鼎鼎的一些迷宫。你需要分析出最好的路线。当然由于迷宫实在太多了，这时候你就得写程序求解。 `X` 代表墙壁。 `#` 代表可以通过的路。 `$` 代表1个金币。 `S` 代表开始点。只有一个起点。 `E` 代表出口。只有一个出口。 `*` 代表锤子，你可以使用一个锤子砸开一个墙壁。你最多持有`1` 个锤子。 你需要求出，对于每个迷宫，能不能通过；如果可以，那么请输出最多能拿到的金币。注意，你不能多次通过一个地方。

第一行一个整数 $t$ ，代表数据组数。 接下来 $t$ 组：第一行每行两个整数 $n,m$ 。 接下来 $n \times m$ 的矩阵描述迷宫。

对于每个迷宫，如果不能通过输出一行 `NO` ,否则输出一个 `YES`，空格输出最大金币数。

|测试点编号 |$m,n$ |$t$ |特殊限制 | 分值| | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | |$1\sim3$ | $\le 3$ | $=1$ | A | 2| |$4\sim5$ | $\le3$ | $=1$ | B | 2| |$6\sim8$ |$\le3$ | $=1$ | C |2| |$9\sim14$ |$\le6$ | $\le4$ | 无 |2| |$15\sim17$ |$\le6$ | $\le4$ | 无 |2| |$18\sim 20$ |$\le 6$ | $\le4$ | A |2| | $21$ | $\le6$ | $\le4$ | B |2| | $22\sim 30$ | $\le 8$ | $\le 4$ | 无 |2| | $31\sim 40$ | $\le9$ | $\le 4$| 无|3| | $41\sim 44$ | $\le9$| $\le8$| C|2| | $45$ | $\le114^{514}$| $\le1919^{810}$| D|2| A:没有墙壁。 B:没有锤子。 C:没有金币。 D:没有迷宫。 保证有 $30\%$ 的数据，最优路径长度 $\le15$。