Problem 6

2012 ACU Programming Contest Series

Problem 6: Maze

The group Altered Competition Ultra (ACU) regularly challenges members to find their way through a diagonal maze.

Write a program to find the shortest path through a diagonal maze field. Members are allowed to start at any northern position and must exit from a southern location to complete the maze.

Input

The first line contains the number of data sets to process.

Each data set begins with a line containing two integers, the height H and width W of the maze (2 ≤ H,W ≤ 100). The following H lines contain either a diagonal wall (indicated by / or \) or open space (indicated by a period).

Output

Output one integer for each data set, the minimum distance travelled from entrance to exit, or if the maze is unsolveable, print "no path".

Sample input:

4
3 10
//////////
//////////
//\/\/\/\/
6 6
////\\
\/////
/////\
\/////
/\\/\/
//\///
4 4
\\//
//.\
\/\\
//\/
3 3
///
///
///

Sample output:

3
14
6
no path