You are given a 2D matrix, and you have to go from top-left to bottom-right. You can only move a cell right or a cell down in each step.
Find out how many paths are there to go from the starting cell to the ending cell.

Example

Matrix Size: 2 rows, 3 columns

M₀₀ M₀₁ M₀₂
M₁₀ M₁₁ M₁₂

We have to go from M₀₀ to M₁₂.

M₀₀ → M₁₀ → M₁₁ → M₁₂ (Down, Right, Right)

M₀₀ → M₀₁ → M₁₁ → M₁₂ (Right, Down, Right)

M₀₀ → M₀₁ → M₀₂ → M₁₂ (Right, Right, Down)

Testing

Input Format

The first line contains a number ‘T’ denoting the number of test cases.
For each test case, one line containing space separated numbers 'n' and ‘m’ denoting the number of rows and columns respectively.

Output Format

For each test case, print a line with the count of all possible paths from top-left to bottom-right.

Examples

Sample Input

3
2 3
3 3
5 5

Expected Output

3
6
70

Constraints

1 <= T <= 1000

1 <= m,n <= 20