Distinct Paths in a Grid with Obstacles

You are given an \(N \times N\) grid which represents a map where each cell is either free (denoted by 0) or blocked by an obstacle (denoted by 1). Starting from the top-left cell \( (1,1)\) (which corresponds to index \( (0,0)\) in 0-indexed arrays), your task is to determine the number of distinct paths to reach the bottom-right cell \( (N,N)\) (or index \( (N-1,N-1)\)).

You are only allowed to move either right or down. If the starting cell is blocked, the number of paths is 0.

The recurrence relation for dynamic programming is given by:

\[ dp[i][j]=\begin{cases} 0,&\text{if } grid[i][j]=1\\ dp[i-1][j]+dp[i][j-1],&\text{otherwise} \end{cases} \]

with the initialization \(dp[0][0] = 1\) (provided \(grid[0][0] = 0\)).

inputFormat

The input is read from standard input (stdin) and has the following format:

• An integer \(T\) representing the number of test cases.
• For each test case:
• An integer \(N\) representing the size of the grid.
• \(N\) lines follow, each containing \(N\) space-separated integers (either 0 or 1) representing the grid. 0 indicates a free cell, while 1 indicates an obstacle.

outputFormat

For each test case, output a single integer on a new line to standard output (stdout) corresponding to the number of distinct paths from the top-left corner to the bottom-right corner following the allowed moves.

## sample

2
3
0 0 0
0 1 0
0 0 0
3
0 1 0
0 1 0
0 0 0

2
1

</p>