HZNUOJ

Maze Problem

Tags:   BFS
Time Limit:  1 s      Memory Limit:   128 MB
Submission:91     AC:46     Score:98.23

Description

Given a maze, find a shortest path from start to goal.

Input

Input consists serveral test cases.

First line of the input contains number of test case T.

For each test case the first line contains two integers N , M ( 1 <= N, M <= 100 ).

Each of the following N lines contain M characters. Each character means a cell of the map.

Here is the definition for chracter.

 

Constraint:

Output

For each test case print one line containing shortest path. If there exists no path from start to goal, print -1.

Samples

input
1 5 5 S-### ----- ##--- E#--- ---##
output
9