Unique Paths in a Grid With Obstacles

You are given an \( n \times n \) grid with some obstacles located on certain cells. The grid is indexed from \( (1,1) \) at the top‐left to \( (n,n) \) at the bottom‐right. You start at cell \( (1,1) \) and need to reach cell \( (n,n) \) while only moving right or down.

Some cells contain obstacles and cannot be traversed. The obstacles are provided as a list of coordinates where each coordinate \( (r, c) \) indicates that the cell at row \( r \) and column \( c \) is blocked. It is guaranteed that the starting cell and destination cell are not blocked.

Your task is to determine the number of unique paths from the starting cell to the destination cell while avoiding obstacles. The answer should be computed using dynamic programming.

Note: The number of obstacles in each test case is provided in the input and you will then receive exactly that many lines of obstacle coordinates.

inputFormat

The first line of the input contains a single integer \( T \) representing the number of test cases.

For each test case:

• The first line contains two integers \( n \) and \( m \), where \( n \) is the size of the grid (forming an \( n \times n \) grid) and \( m \) is the number of obstacles.
• The next \( m \) lines each contain two integers \( r \) and \( c \), indicating that cell \( (r, c) \) is blocked.

You may assume that \( 1 \le n \le 100 \) and \( 0 \le m \le n^2 - 2 \) (the start and destination cells are never blocked).

outputFormat

For each test case, output a single line with one integer representing the number of unique paths from \( (1,1) \) to \( (n,n) \) that avoid obstacles.

## sample

1
2 0

2

</p>