Taco's Grid Path

You are given an integer N and an N x N grid representing a field. Each cell in the grid contains either 0 or 1, where 0 indicates a free cell and 1 indicates an obstacle.

You start at the top-left cell (0, 0) and want to reach the bottom-right cell (N-1, N-1). However, you can only move in two directions: right and down. Your task is to determine whether a valid path exists from the start to the destination without passing through any obstacles.

Formally, decide if there exists a sequence of moves from (0,0) to (N-1,N-1) using only moves of the form \( (i, j) \to (i, j+1) \) or \( (i, j) \to (i+1, j) \) such that every visited cell contains 0.

inputFormat

The input begins with an integer T, the number of test cases. Each test case starts with an integer N on a new line representing the size of the grid. This is followed by N lines, each containing N space-separated integers (either 0 or 1) which represent the grid.

outputFormat

For each test case, output a single line containing YES if a valid path exists from the top-left to the bottom-right corner, or NO otherwise.

1
4
0 0 1 0
1 0 1 0
0 0 0 0
1 1 0 0

YES