Count Grid Paths

Given an n x m grid, you are to determine the number of distinct paths from the top-left corner to the bottom-right corner if you can only move to the right or down at each step.

The answer can be computed via the combinatorial formula \[ C(n+m-2,\;n-1)\] which represents the number of ways to choose when to move down among the total moves.

For example:

• For a 2 x 2 grid, the answer is 2.
• For a 3 x 2 grid, the answer is 3.
• For a 3 x 3 grid, the answer is 6.

inputFormat

The first line contains an integer T, the number of test cases.

Each of the next T lines contains two space-separated integers n and m, representing the number of rows and columns of the grid respectively.

outputFormat

For each test case output a single integer – the number of ways to reach the bottom-right corner of the grid.

## sample

6
2 2
3 2
3 3
1 1
1 1000
1000 1

2
3
6
1
1
1

</p>