题目描述

迷宫由 $R \times C$ 个方格组成，其中 S 表示起点，E 表示终点，. 表示可以通行的方格，# 表示墙壁。

每次可以从当前方格移动到上、下、左、右相邻的可通行方格。请计算从 S 到 E 最少需要移动多少步。

输入格式

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

每组数据的第一行包含两个整数 $R,C$。

接下来 $R$ 行，每行包含一个长度为 $C$ 的字符串，描述迷宫。每个迷宫中有且仅有一个 S 和一个 E。

输出格式

对于每组数据，若可以到达终点，输出一行一个整数，表示最少移动步数；否则输出 oop!。

样例

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

5
1
oop!

数据范围与提示

• $1 \le T \le 10$
• $2 \le R,C \le 200$