After you helped Xiao I defeat Xiao J on the train, Xiao J was very unconvinced and decided to challenge Xiao I to another game. This time, Xiao J brought out his prized collection of chocolates.

Xiao J has prepared $(N + 1)$ bars of chocolate. Except for the $(N + 1)$-th bar, which has $M$ pieces, the $i$-th bar has exactly $i$ pieces.

The game is played by Xiao I and Xiao J, with Xiao I going first. Players take turns, and in each turn, a player can perform the following operation: Choose a chocolate bar and divide it into three ordered segments (left, middle, and right). Each segment must consist of an integer number of pieces, the middle segment cannot be empty, while the left and right segments can be empty. Eat the middle segment and return the left and right segments to the game.

When a player cannot make a move because there are no chocolates left, that player loses.

At the start of the game, Xiao I has not yet calculated the optimal strategy, and Xiao J is rushing him. Therefore, Xiao I chooses one of all possible legal operations uniformly at random. Xiao J, having prepared for this, plays optimally on every turn. After this initial random move, Xiao I finally figures out the game strategy and plays optimally for all subsequent turns.

Xiao I wants to know how many of the possible first moves allow him to win the game. The answer can be very large, so you only need to output the result modulo $(10^9 + 7)$.

Two operations are considered different if and only if the chosen chocolate bar is different, or if the number of pieces in any of the three segments (left, middle, right) is different.

Input

The input is read from standard input. There are multiple test cases. The first line contains an integer $T$, representing the number of test cases. Each test case is then provided. Each test case consists of a single line containing two integers $N$ and $M$, as described in the problem statement.

Output

Output to standard output. For each test case, output a single integer representing the number of first moves that lead to a win for Xiao I, modulo $(10^9 + 7)$.

Examples

Input 1

4
3 0
3 1
3 12345678987654321
0 0

Output 1

0
4
450617288
0

Note

• For the first test case, it is easy to prove that the first player is in a losing position, so Xiao I will lose regardless of his move.
• For the second test case, there are four possible operations:
  • Divide the first bar into $(0, 1, 0)$ and eat the middle segment;
  • Divide the fourth bar into $(0, 1, 0)$ and eat the middle segment;
  • Divide the third bar into $(0, 1, 2)$ and eat the middle segment;
  • Divide the third bar into $(2, 1, 0)$ and eat the middle segment.
• For the third test case, all legal operations involve dividing the fourth bar into three segments such that the left and right segments have the same length.
• For the fourth test case, the game is just a facade; Xiao J simply wants Xiao I to lose.

Subtasks

This problem has only one test case with $T = 5 \times 10^4$, where for each test case $0 \le N, M \le 10^{18}$.

Note

"Can we continue playing games with you next time..."