Unique Paths in a Grid with Obstacles

You are given a grid of dimensions \(n \times m\) where each cell is either free (represented by 0) or blocked (represented by 1). The task is to determine the number of unique paths from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((n-1,m-1)\)) if the robot can only move either down or right at any point in time.

The transition is defined by the recurrence:

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

Note that if the starting cell or the ending cell is blocked, the answer is 0.

inputFormat

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

• The first line contains an integer \(T\), representing the number of test cases.
• Each test case starts with a line containing two integers \(n\) and \(m\) (the number of rows and columns, respectively).
• This is followed by \(n\) lines, each containing \(m\) integers (0 or 1) separated by spaces, representing the grid.

outputFormat

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

## sample

1
3 3
0 0 0
0 1 0
0 0 0

2

</p>