Treasure Hunt: Find the Safe Path

You are given an $N\times N$ grid where each cell is either safe or unsafe. A cell containing 1 is safe, and a cell containing 0 is unsafe. Your task is to determine whether there exists a safe path from the top-left cell (i.e., cell at position $(0,0)$) to the bottom-right cell (i.e., cell at position $(N-1,N-1)$). You can move in four directions: up, down, left, and right. The path is valid if:

• The starting cell and the destination cell are safe.
• All visited cells in the path are safe.

If such a path exists, output YES; otherwise, output NO.

Note: The moves are allowed only in the four cardinal directions, and you cannot move diagonally.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

T
N
row1
row2
... 
rowN
N
row1
row2
... 
rowN
...

Where:

• T is the number of test cases.
• For each test case, the first line contains an integer N — the size of the grid.
• The next N lines each contain N integers (either 0 or 1) separated by spaces representing the grid.

outputFormat

For each test case, output a single line to standard output (stdout) containing either YES if a safe path exists from the top-left to the bottom-right corner, or NO if it does not.

## sample

4
1
1
1
0
3
1 0 1
1 1 0
0 1 1
3
1 0 1
0 0 0
1 1 1

YES
NO
YES
NO

</p>