Background
In the distant planet Omicron Persei 8, there is a huge ocean of rotten dark water. In the middle of the ocean, there is the island of Nevreturn, where the damned Omicronian prisoners are sent. And on the island, there is an intricate labyrinth; only those prisoners who are able to escape from the labyrinth are given the merciful death. The labyrinth is surrounded by a deep abysm, where the mythical Sapitaur –half frog, half bull– lives, eating all those Omicronians who took a wrong course in the labyrinth.
You are an unfortunate Omicronian prisoner. Will you be able to escape from the labyrinth?
The Problem
Sapitaur’s Labyrinth consists of a matrix of cells. There are two kinds of cells, as shown in the figure below:
NOWSE. There is a wall extending from the NorthWest of the cell to the SouthEast.
NESOW. There is a wall extending from the NorthEast of the cell to the SouthWest.
Left: the two kinds of cells. Middle: a sample labyrinth with 3x3 cells, and 2 paths to escape. Right: a labyrinth with 15x10 cells, and only 1 path to escape (in red).
As you can see in the figure above, the entrance to the labyrinth is in the north (the upper row of the matrix), the exit is in the south (the lower row of the matrix), and the abysm extends along both sides of the labyrinth (beyond the first and last column of the matrix).
You have to count how many different paths exist to go from the entrance to the exit of the labyrinth. Obviously, these paths cannot go through the abysm.
The Input
The first line of the input contains an integer M, indicating the number of test cases.
For each test case, the first line contains two integers N M, between 1 and 500, where N is the width of the labyrinth (number of columns) and M is the height (number of rows). M lines follow; each line has N characters: “\” for NOWSE cells; and “/“ for NESOW cells.
The Output
For each test case, the output should consist of an integer indicating the number of different paths from the entrance to the exit of the labyrinth.
Sample Input


Sample Output


Solution
題目描述：
給定用 \
、/
構成的迷宮，找到從上方進入且可以抵達下方的路徑總數。
題目解法：
這題目看似非常難，由於在建表處理上非常不方便。
但是仔細想想，考慮當前所在的格子類型，再考慮進來的方向，就能推出下一步會到達的格子。
(類似於鏡子反射的現象)
路徑總數不會太多，直接使用 DFS 進行搜索枚舉即可。

