Maze Navigation with Obstacles

You are given a grid of size \( M \times N \) which represents a maze. Each cell in the grid can either be open (denoted by 0) or blocked by an obstacle (denoted by 1). Your task is to determine the number of unique paths from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((M-1, N-1)\)). The robot can only move right or down at any step. If the starting or ending cell is blocked, then the answer is 0.

Note: Use dynamic programming to efficiently calculate the number of paths. The state transition is governed by the relation:

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

Make sure that the solution reads input from standard input (stdin) and writes the result to standard output (stdout).

inputFormat

The input is read from stdin and is formatted as follows:

1. The first line contains a single integer \( T \) representing the number of test cases.
2. For each test case:
   1. The first line contains two integers \( M \) and \( N \) separated by a space indicating the dimensions of the grid.
   2. The next \( M \) lines each contain \( N \) integers (either 0 or 1) separated by spaces representing a row of the grid.

outputFormat

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

## sample

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

2
1

</p>