Description

Algernon is a clever yet lazy little white mouse, whose greatest skill is navigating through all kinds of mazes.
Today, it is about to tackle a very large maze. To encourage Algernon to reach the endpoint as quickly as possible, the researchers have placed a piece of Algernon's favorite cheese at the destination. Now, the researchers want to know: if Algernon is smart enough, what is the minimum time it needs to reach the cheese?

The maze is represented by an R×C character matrix. The character S denotes Algernon's starting position, E represents the location of the cheese, # stands for walls, and . indicates passable areas.

Algernon can move from its current position to any of the four adjacent cells (up, down, left, or right) in one unit of time, but it cannot move outside the boundaries of the map.

Input Format

The first line is a positive integer T (1 ≤ T ≤ 10), indicating the number of test cases.
For each test case, the first line contains two positive integers R and C (2 ≤ R, C ≤ 200), separated by a space, representing that the map is an R×C matrix.
The following R lines describe the specific content of the map, with each line containing C characters. The meanings of the characters are as described in the problem statement. It is guaranteed that there is exactly one S and one E.

Output Format

For each test case, output the minimum number of time units Algernon needs to reach the cheese. If Algernon cannot reach the cheese, output "oop!" (only the content inside the quotes, without the quotation marks). Each test case's output should occupy a single line.

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

5
1
oop!