Unique Paths in a Grid

Given a grid of size N x M, you are required to calculate the number of unique paths from the top-left corner (1, 1) to the bottom-right corner (N, M). At each step, you may only move either right or down.

The number of unique paths is given by the binomial coefficient:

\( \displaystyle \text{Paths} = \binom{N+M-2}{N-1} \)

where \( \binom{n}{k} \) denotes the number of ways to choose \( k \) elements from \( n \) elements.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer T, the number of test cases. Each of the following T lines contains two positive integers N and M separated by a space.

outputFormat

For each test case, output the number of unique paths on a separate line to standard output (stdout).## sample

3
2 2
3 3
1 5

2
6
1