Write a program that simulates a mouse in a maze. The program must count all the number of paths the mouse can take from the starting point to the final point, and the shortest step count among these paths.
The maze type is shown in following figure:
S$###
$$#$$
$$$##
##$$F
it consists of S (starting point), #(wall), $(road) and F (final point). The mouse can move in the four directions: up, down, left, and right. Note that each $(road) can only be passed for one time in each path.
If there is no way from S to F, then print 0 -1.
The first line has an integer N(1<=N<=3), which means the number of test cases.
For each case, the first line has two integers. The first and second integers R and C (4<=R, C<=100) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.
The following R lines, each containing C characters, specify the elements of the maze.
Please output the possible path counts from S to F, followed by the shortest step count among these paths. It is guaranteed that the possible paths counts won't exceed 100000.