Unique Paths with Obstacles

Given an m \times n grid, some cells of which contain obstacles (represented by 1) while others are open (represented by 0), determine the number of unique paths from the top-left corner to the bottom-right corner of the grid. You may only move either down or right at any point in time. Formally, if we denote the number of ways to reach cell \((i, j)\) as \(dp[i][j]\), then the recurrence relation 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} $$

If the starting cell \(grid[0][0]\) has an obstacle, then there are no valid paths. Similarly, if the destination cell has an obstacle, the answer is zero.

inputFormat

The first line of input contains an integer t denoting the number of test cases. For each test case, the first line contains two integers m and n representing the number of rows and columns in the grid respectively. This is followed by m lines, each containing n space-separated integers. Each integer is either 0 (an open cell) or 1 (an obstacle).

outputFormat

For each test case, output a single integer on a new line representing the number of unique paths from the top-left corner to the bottom-right corner of the grid, while avoiding obstacles.

## sample

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

2
1

</p>