题目描述

阿尔吉侬是一只小白鼠，它要在迷宫中找到奶酪。迷宫由 R 行 C 列构成，S 表示它的位置，E 表示奶酪，# 表示墙，. 表示空地。

它每单位时间可以向上下左右移动一格，不能穿墙或走出地图。求它吃到奶酪的最少时间。

输入格式

第一行测试组数 T。每组数据第一行 R,C，接下来 R 行，每行 C 个字符。

输出格式

每组输出一行，能到达则输出最少时间，不能到达则输出 oop!。

样例

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

5
1
oop!

数据范围

1≤T≤10，2≤R,C≤200。每组地图恰有一个 S 和一个 E。