Description

勇者闯想要打败魔王肖，但是以他目前的实力是远远不够的。神明告诉勇者闯：“在世界尽头的恩帕萨特大迷宫里有位圣者航，他拥有这个世界的本源之力。但是他因为要守护大地的稳定，无法离开。若是你能向圣者航借到本源之力，你将拥有足够的力量打败魔王肖。我这里有一张迷宫地图，还有一个一次性的任意门。你可以通过地图找到他，拿到本源之力之后你可以通过一个传送阵到达你的下一个任务点。”传送阵的地点也在地图中标出。任意门的作用是你可以通过任意门瞬间到达任意一个你曾经到达过的地点。

地图信息如下：地图描述了一个n 行m 列的地图，其中'#'号代表墙壁，'.'代表路，'x'代表陷阱（进入陷阱会昏迷3秒且陷阱不会消失），'s'代表某闯现在的位置，'z'代表圣者航的位置，'w'代表传送阵的位置，其中's','z','w'为坐标不同的点，勇者闯起始位置不与陷阱'x'重合也不与墙壁'#'重合。

地图描述就是这样，有什么不懂的就直接问神明吧！

勇者闯每次可以向上下左右四个方向移动一格（当然不能走出地图之外，也不能撞墙）。每移动一次花费一秒，请你规划一条路线，使得勇者闯先找到圣者航然后到达传送阵的用时最短，请合理使用一次性任意门，当然也可以选择不用。

勇者闯想知道他从开始到找到圣者航，再到传送阵所需要消耗的最少的时间。

Input Format

第一行输入一个数T表示测试样例数 (1≤T≤3）。

对于每组样例：

输入n+1行，

第一行输入两个整数n, m，表示的迷宫大小(3≤n,m≤7)；

接下来n行描述迷宫。

Output Format

对于每组样例：

输出一行，该行表示勇者闯所花费的最短时间，如果不能到达请输出-1。

2
3 4
w#x.
#x..
s..z
4 7
.#xxx##
.#x.xw.
.#xxxxx
x#sx.z#

-1
11

2
7 3
xx.
#x#
s..
z.x
..x
..x
wx#
7 3
s#x
##.
xz.
.xx
#x.
#xw
x##

4
-1

Source

1816 Online Judge 10.100.0.232