Changu and Mangu were playing volleyball when they were handed a very easy question about the game. You can help them solve it.

In volleyball 2 teams play with initial score 0 and each team gets points which increases their scores by 1. 

The game ends when:

One of the teams gets 25 points and another team has < 24 points ( strictly less than 24).

If the score ties at 24:24, the teams continue to play until the absolute difference between the scores is 2.

Given the final score of a game ( A B ) i.e., the first team has scored A points and the second has scored B points,

You have to find the number of different sequences of getting points by teams that leads to this final score?

 

Input

The first line contains the number of test cases T. The next T lines contain two integers A and B.

Output

Output the number of different sequences of getting points by the teams that leads to the final score A : B. Final means that the game should be over after this score is reached. If the number is larger than 109+7, output number modulo 109 + 7. Print 0 if no such volleyball game ends with the given score.

Example

Input:

2

3 25

24 17

 Output:

2925 

0

Constraints:

T<=15

0 ≤ A , B ≤ 109