Unique Paths in a Grid

Given an m x n grid, you are required to calculate the number of unique paths from the top-left corner to the bottom-right corner. At each step, you can only move either down or right.

The relation used in the solution is given by the recurrence:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\), with the base cases \(dp[i][0] = 1\) and \(dp[0][j] = 1\) for all valid indices.

It is guaranteed that the input values are such that a dynamic programming solution will compute the answer efficiently.

inputFormat

The first line of input contains an integer T, the number of test cases. Each test case consists of a single line containing two space-separated integers m and n, representing the number of rows and columns of the grid respectively.

For example:

3
2 2
3 3
3 7

outputFormat

For each test case, output a single integer that denotes the number of unique paths for the given grid. Each answer should be printed on its own line.

For the above input, the output should be:

2
6
28

## sample

3
2 2
3 3
3 7

2
6
28

</p>