Unique Paths in a Grid with Obstacles

You are given an n×n grid. Starting from the top-left corner (cell (0, 0)), your goal is to reach the bottom-right corner (cell (n-1, n-1)).

You can only move either right or down at any step. However, some cells contain obstacles and cannot be walked on. The obstacles are specified as a list of coordinates in 0-indexed format. If the starting cell is blocked, then there is no valid path.

The number of unique paths, if there is no obstacle, is governed by the recurrence relation:

$$dp(i, j) = dp(i-1, j) + dp(i, j-1)$$

For cells containing an obstacle, treat dp(i, j) as 0. Solve the problem using dynamic programming.

inputFormat

The input is given via stdin and has the following format:

• The first line contains a single integer T representing the number of test cases.
• For each test case, the first line contains an integer n indicating the size of the grid (n×n).
• The next line contains an integer m denoting the number of obstacles.
• Then follow m lines, each with two space-separated integers x and y representing the coordinates of an obstacle.

Note: All coordinates are given in 0-indexed format.

outputFormat

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

## sample

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

2
0

</p>