Grid Paths with Obstacles

You are given one or more grid configurations. Each grid is represented by a matrix where 0 indicates a free cell and 1 indicates an obstacle. Your task is to compute the number of unique paths from the top‐left corner to the bottom‐right corner of the grid, moving only right or down. If either the starting cell or the destination cell is blocked, then the result is 0.

The problem can be solved using dynamic programming. The recurrence relation used is as follows:

$$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 base condition \(dp[0][0] = 1\) (if the starting cell is free).

inputFormat

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

T
n1 m1
row1
row2
... (n1 rows, each with m1 integers separated by spaces)
n2 m2
row1
row2
... (n2 rows)
...

Here, T is the number of test cases. Each test case starts with two integers, n and m, denoting the number of rows and columns in the grid, followed by n lines describing the grid.

outputFormat

For each test case, output the number of unique paths from the top-left to the bottom-right on a new line, written to standard output (stdout).

## sample

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

2
1
0
1

</p>