Unique Paths in an Obstacle Grid

You are given a 2D grid grid consisting of 0s and 1s. A 0 represents a walkable cell, and a 1 represents an obstacle. Your task is to compute the number of unique paths from the top-left cell to the bottom-right cell of the grid, moving only either down or right at any point in time.

If the starting cell or the destination cell contains an obstacle, then no valid path exists, and you should return 0.

The problem can be solved using Dynamic Programming. Define $dp[i][j]$ as the number of unique ways to reach cell $(i, j)$. The recurrence relation is:

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

Make sure to handle the edge cases properly, such as grids of size 1x1.

inputFormat

The input is read from stdin. The first line contains an integer T representing the number of test cases. For each test case:

• The first line contains two space-separated integers n and m denoting the number of rows and columns in the grid, respectively.
• The next n lines each contain m space-separated integers (either 0 or 1) representing the grid.

outputFormat

For each test case, output a single integer on a new line that represents the number of unique paths from the top-left to the bottom-right of the grid. The output should be printed to stdout.

## sample

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

2
0

</p>