Unique Paths With Obstacles

Given a grid of size \(m \times n\) where some cells contain obstacles, determine the number of unique paths a robot can take from the top-left corner to the bottom-right corner. The robot is only allowed to move either down or right at any point in time. An obstacle and a free cell are indicated by a 1 and 0 respectively.

In mathematical terms, if \(dp[i][j]\) represents the number of ways to get to cell \((i,j)\), then:

[ \begin{aligned} dp[i][j] &= 0, \quad \text{if } grid[i][j] = 1, \ dp[i][j] &= dp[i-1][j] + dp[i][j-1], \quad \text{otherwise with appropriate boundary conditions.} \end{aligned} ]

If the start or end cell is blocked, the answer is 0.

inputFormat

The first line contains an integer \(t\) indicating the number of test cases. For each test case:

• The first line contains two space-separated integers \(m\) and \(n\), representing the dimensions of the grid.
• The next \(m\) lines each contain \(n\) space-separated integers (either 0 or 1) representing the grid where 0 denotes an empty cell and 1 denotes an obstacle.

outputFormat

For each test case, output a single integer representing the number of unique paths from the top-left corner to the bottom-right corner, each printed on a separate line.

## sample

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

2
0
6
0

</p>