Description
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.
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.
The above case has 4 different paths from S to F as follows:
If there is no way from S to F, then print -1.
Input
The first line has an integer N(1<=N<=10^6), which means the number of test cases.
For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) 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.
Output
Print out all the number of paths for each case, and there is a new line character at the end of each line.