This problem is a programming version of Problem 15 from projecteuler.net
Starting in the top left corner of a grid, and only being able to move to the right and down, there are exactly routes to the bottom right corner.
How many such routes are there through a grid? As number of ways can be very large, print it modulo .
Input Format
The first line contains an integer , i.e., number of test cases.
Next lines will contain integers and .
Constraints
Output Format
Print the values corresponding to each test case.
Sample Input
2
2 2
3 2
Sample Output
6
10
Explanation
For as shown in statement above.