Unique Paths in a Grid

Given an M x N grid, your task is to determine the number of unique paths from the top-left corner to the bottom-right corner. You are only allowed to move either down or right at any step.

This problem can be solved using a dynamic programming approach. Define a DP table \(dp[i][j]\) where each cell represents the number of unique ways to reach that cell from the top-left corner. The recurrence relation is given by:

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \)

with the base conditions \(dp[i][0] = 1\) for all \(i\) and \(dp[0][j] = 1\) for all \(j\).

Compute and output the number of unique paths for each grid provided in the input.

inputFormat

The first line of input contains a single integer (T) denoting the number of test cases. Each of the following (T) lines contains two space-separated integers (M) and (N), representing the number of rows and columns in the grid respectively.

outputFormat

For each test case, output a single line containing the number of unique paths from the top-left to the bottom-right corner.## sample

3
2 2
3 7
1 10

2
28
1