Unique Paths in a Minefield

You are given a grid representing a minefield. The grid contains 0s and 1s, where 0 represents a free cell and 1 represents a landmine. A robot starts from the top-left corner and must reach the bottom-right corner. The robot can only move either right or down at any step. The task is to determine the total number of unique paths the robot can take to get from the start to the finish without stepping on a landmine.

If a mine is present at the starting cell or the destination cell, then there is no valid path. The number of ways can be calculated using dynamic programming with the recurrence relation:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) for cells without a mine,

with the base condition \(dp[0][0] = 1\) (provided the cell is not a mine). If the current cell contains a mine (grid[i][j] = 1), then \(dp[i][j] = 0\).

This problem tests your ability to implement grid-based dynamic programming with boundary conditions and obstacle handling.

inputFormat

The first line contains an integer T representing the number of test cases.

Each test case begins with two integers n and m (the number of rows and columns in the grid, respectively). This is followed by n lines, each containing m space-separated integers (each integer is either 0 or 1) representing the grid.

Example:

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

This sample input corresponds to 4 test cases.

outputFormat

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

Example Output for the above input:

2
1
0
1

## sample

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

2
1
0
1

</p>