#1609 DiceRotation

39  1 s   128 MB  

Description

Cat Taro likes dice. He has a die which is a 1 x 1 x 1 cube where each face contains a number between 1 and 6. Each number appears on exactly one face, and the sum of the numbers on opposite faces is always 7. 



There is an infinitely large board which is divided into 1 x 1 cells. The board has a coordinate system in which the x-coordinate (the first coordinate) increases from left to right, while the y-coordinate (the second coordinate) increases from bottom to top. Taro initially places the die on the cell with coordinates (0, 0). The die shows '1' on the top face, '2' on the front face, and '3' on the left face (so the bottom face shows '6', the back face shows '5', and the right face shows '4'). 



Taro wants to move this die to cell (goalxgoaly) by performing a sequence of rotations. There are two ways to rotate the die:

For example, if Taro's first rotation is toward the right, then the die will move to cell (1, 0) and the top face will show '3'. 



 



Print the number of sequences of rotations which move the die to cell (goalxgoaly), such that the following conditions are satisfied:

The answer will always fit in a signed 32-bit integer.

Input

The first line of the input gives the number of test cases, T (1 <= T <= 500).

For each test case, two integers goalx and goaly will be given in one line. goalx and goaly will each be between 1 and 1,000,000,000, inclusive.

Output

For each test case, print calculated number of cases, in one line.

Sample Input

Sample Output

5
2 2
5 8
47 58
489 489
1000000000 1000000000
2
2
2
2
2