Mangu bought a new garden for himself. The garden is shown below in the image. The garden is semi infinite i.e. infinite in two directions (+x direction and +y direction). Garden's square cells are indexed as in the diagram. Changu comes to visit Mangu and see his garden. He is standing initially on (0, 0). From a particular cell he can travel in 8 directions if possible. His task is to go from (0, 0) to (n, k) in n steps. Your task is to calculate the number of possible paths he can take.

Input

The first line contains the number of test cases, T. The next T lines contain two integers n and k separated by a single space.

Output

You have to print the number of possible paths modulus 1000000007.

Example

Input:
2
1 1
2 0

Output:
1
2

Explanation

The possible paths for two case are shown below:

Case 1:

Case 2:

Constraints:

T<10^5

0<=N<7000

0<=K<=N