Time Limit: 10000msMemory Limit: 32768K


我是你最可怕的噩梦

                  ——泰达米尔

做了一个噩梦。他梦到自己被困在一个迷宫里,而且身上绑了一个定时炸弹,过不了多久就要爆 炸了。这个迷宫可以看做一个的矩阵,在迷宫某处有一个出口。他必须在炸弹爆炸前跑出去才有可能得救。但是他又不能跑太快以免导致炸弹提前爆炸,于是,他每分钟只能向相邻的区域移动。同时,有些区域有时间重置装置,可以将他身上是炸弹的剩余时间回复到初始状态。
每天努力的刷题还是有用的,伟大的代码之神给了这个迷宫的地图,这至少让他不用盲目的跑了:),但是能不能跑出去就另说了
这块地图是一个的字符,不同字母含义如下:

是一个很懒的人,梦里也是一样,他想让你们告诉他他有没有机会跑出去。“要是无论如何也跑不出去,那也不用累死累活的往外跑了,干脆就在这里刷刷题。”他自抱自弃的想着。

输入

第一行是一个整数,代表样例数。接下来每个样例中第一行有3个整数分别代表地图的行数列数以及炸弹初始的时间。接下来行每行一个长度为的字符串,代表地图。

输出

对于每组, 如果无法逃出迷宫,则输出(不要引号),否则,输出所需的最少时间。

3
3 3 6
S..
..W
..E
4 8 6
S..W..WW
.WR..WR.
.WWWWWW.
...R...E
5 8 6
.S.....R
.WWW.WW.
.R.W..W.
.WWWWEW.
..R.....

4
Poor RunningPhoton!
13