Unique Paths with Obstacles

Given a grid of size \(N \times M\) with some cells blocked, your task is to determine the number of unique paths from the top-left corner to the bottom-right corner of the grid. You can only move either right or down at any point in time. A blocked cell is marked by the value 1, and an open cell is marked by 0.

The problem can be formulated using a dynamic programming approach where the number of paths to reach cell \((i, j)\) is the sum of the paths to reach \((i-1, j)\) and \((i, j-1)\), provided that the cell \((i, j)\) is not blocked. Formally, the recurrence is given by:

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

Note that if the starting cell or the destination cell is blocked, then the number of unique paths is zero.

inputFormat

The first line of input contains an integer \(T\) denoting the number of test cases. Each test case begins with a line containing three integers \(N\), \(M\), and \(K\) where \(N\) and \(M\) represent the number of rows and columns in the grid respectively, and \(K\) is the number of blocked cells. This is followed by \(K\) lines, each containing two integers \(x\) and \(y\) representing the 1-indexed coordinates of a blocked cell.

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.

## sample

2
3 3 1
2 2
3 3 2
2 2
3 3

2
0

</p>