Pathfinding in a Grid

You are given a grid with n rows and m columns. Each cell is either open (represented by .) or blocked (represented by #). Your task is to determine whether there exists a path from the top-left cell (position (0,0)) to the bottom-right cell (position (n-1, m-1)). You may move up, down, left, or right. The solution should use a breadth-first search (BFS) strategy.

Note: The grid indices satisfy \(0 \le i < n\) and \(0 \le j < m\). The starting cell and the target cell must be open in order to have a valid path.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each test case consists of:

• A line with two integers n and m, the number of rows and columns respectively.
• n subsequent lines, each containing m characters separated by spaces. Each character is either . (open) or # (blocked).

outputFormat

For each test case, output a single line containing YES if there is a path from the start to the end, or NO if there is not.

## sample

4
3 3
. . .
. # .
. . .
3 3
. # .
# # .
. . .
1 1
.
1 1
#

YES
NO
YES
NO

</p>