小明进入地下迷宫寻找宝藏，找到宝藏后却发生地震，迷宫各处产生岩浆，小明急忙向出口处逃跑。

如果丢下宝藏，小明就能迅速离开迷宫，但小明并不想轻易放弃自己的辛苦所得。

所以他急忙联系当程序员的朋友你（当然是用手机联系），并告诉你他所面临的情况，希望你能告诉他是否能成功带着宝藏逃脱。

有多组测试数据。

每组测试数据第一行是一个整数 $T\ (1 \leq T \leq 10)$，代表接下去的例子数。

接下来是 $T$ 组例子。

每组例子第一行是两个整数 $N,M\ (1 \leq N,M \leq 1,000)$。代表迷宫的大小有 $N$ 行 $M$ 列。

接下来是一个 $N*M$ 的迷宫描述。

S 代表小明的所在地。

E 代表出口,出口只有一个。

. 代表可以行走的地方。

! 代表岩浆的产生地。（这样的地方会有多个，其个数小于等于 $10,000$）

# 代表迷宫中的墙，其不仅能阻挡小明前进也能阻挡岩浆的蔓延。

小明携带者宝藏每秒只能向周围移动一格，小明不能碰触到岩浆（小明不能和岩浆处在同一格）。

岩浆每秒会向四周不是墙的地方蔓延一格。

小明先移动完成后，岩浆才会蔓延到对应的格子里。

小明能移动到出口，则小明顺利逃脱。