Path Existence in Grid Maze

You are given a grid maze represented by a matrix with N rows and M columns. Each cell of the matrix is either free (denoted by .) or blocked (denoted by #). Your task is to determine whether there exists a valid path from the top-left corner (cell (0,0)) to the bottom-right corner (cell (N-1, M-1)).

The allowed moves are to the right or down only. More formally, starting from cell \( (0,0) \), you can move to cell \( (i,j) \) if and only if you move to \( (i+1,j) \) or \( (i,j+1) \). The path is valid only if all visited cells are free (i.e. contain .), and the first and last cells must be free.

Note: In some cases, the grid might be as small as a single cell.

Input Constraints: \(1 \leq N, M \leq 10^3\). The grid is provided as input with each row on a separate line.

inputFormat

The first line contains a single integer \(T\) representing the number of test cases. For each test case, the first line contains two space-separated 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\) consisting of characters . (free cell) or # (blocked cell).

Example:

2
3 3
... 
.#.
...
3 3
.#.
##.
...

outputFormat

For each test case output a single line: "YES" if there exists a valid path from the top-left cell to the bottom-right cell; otherwise, output "NO".

Example:

YES
NO

## sample

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

YES
NO
YES

</p>