Pathfinding in a Grid

You are given a grid of size \(N \times M\) consisting of the characters 'W' (wall), '.' (empty space) and 'S' (starting point). Your task is to determine whether it is possible to reach the top-left corner (cell \((0,0)\)) starting from the cell marked with 'S', moving only in four directions (up, down, left, right) and avoiding cells marked as walls.

The grid may contain only one starting point. If there is no starting point, or if the path is blocked by walls, then the answer is False.

Note: When exploring the grid, you cannot move outside the grid boundaries. It is allowed to modify the grid (for example, mark visited cells) during the search, as long as it helps to avoid cycles.

inputFormat

The first line of input contains a single integer \(T\) denoting the number of test cases. For each test case, the first line contains two integers \(N\) and \(M\) representing the number of rows and columns, respectively. This is followed by \(N\) lines, each containing a string of length \(M\) with characters from the set {'W', '.', 'S'} that describe the grid.

outputFormat

For each test case, output a single line containing either True or False (without quotes) indicating whether it is possible to reach the top-left cell \((0,0)\) from the starting cell.

## sample

5
4 4
.W..
.WW.
...W
SW.W
3 3
.W.
WW.
S..
1 1
S
2 2
W.
S.
2 2
..
S.

True
False
True
False
True

</p>