A Bouquet for Algernon

Problem Background

Special for beginners, ^_^

Problem Description

Algernon is a clever but lazy little white mouse, best known for walking all kinds of mazes. Today he is taking on a very large maze, and to encourage him to reach the end quickly, the researchers placed a piece of his favourite cheese at the destination. The researchers now want to know: if Algernon is smart enough, what is the minimum time he needs to eat the cheese?

The maze is a character matrix of size $R \times C$. The character S marks Algernon's position, E marks the cheese, # marks a wall, and . marks a passable cell. In one unit of time Algernon can move from his current cell to any of the four orthogonally adjacent cells, but he must not step outside the map boundary.

Input Format

The first line is a positive integer $T$ ($1 \le T \le 10$): the number of test cases.

Each test case begins with one line containing two space-separated positive integers $R$ and $C$ ($2 \le R, C \le 200$), meaning the map is an $R \times C$ matrix.

The following $R$ lines describe the map, each containing $C$ characters as explained above. There is exactly one S and exactly one E.

Output Format

For each test case, print the minimum number of time units Algernon needs to reach the cheese. If he cannot reach it, print oop!. Each test case's answer goes on its own line.

Sample Input

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

Sample Output

5
1
oop!

Constraints

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

Time limit $1$ s, memory $1024$ KiB per test case.

Hint

• One BFS per test case. If the BFS finishes without ever reaching E, output oop! (exactly, lowercase) instead of a number.