A. Mission Hexa
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are an elite mercenary who has infiltrated the legendary beehive of the Queen Bee. The hive is built from regular hexagonal cells arranged in concentric layers around the queen's chamber at the center. The central cell is numbered $$$0$$$.

The hive has $$$(n + 1)$$$ layers numbered from $$$0$$$ to $$$n$$$. Layer $$$0$$$ contains only the queen's chamber (cell $$$0$$$). For every integer $$$x \: (1 \le x \le n)$$$, layer $$$x$$$ is defined as the set of cells that are adjacent to at least one cell of layer $$$(x - 1)$$$ and are not part of any smaller layer. Each layer surrounds the previous (except layer $$$0$$$) and is surrounded by the next (except layer $$$n$$$).

The cells are numbered layer by layer outward from the center. Within each layer, the numbering starts at the topmost cell of that layer. Numbering proceeds clockwise for odd-numbered layers and counter-clockwise for even-numbered layers.

You are currently at the queen's chamber at cell $$$0$$$. Your mission is to kill the queen, and then escape the beehive from cell $$$k$$$.

Every cell other than the queen's chamber houses a guard bee. If a single guard bee anywhere in the hive is alive at the moment you exit the queen's chamber, you will be detected and killed immediately. Therefore, any bee that remains alive while you leave the center is fatal.

From the queen's chamber, you can use a powerful laser gun and fire any number of shots. Each shot is a perfect straight ray that originates at the center of the queen's chamber and extends to infinity in some direction. A shot kills a guard bee if and only if the center of that bee's cell lies exactly on the line of fire. The shot must be fully precise: if the center of a cell is missed by even the smallest amount, the guard bee in that cell remains alive.

After killing the queen and all the guards, you will walk from cell $$$0$$$ to cell $$$k$$$ along adjacent cells. A path is a sequence of cells where each consecutive pair of cells is adjacent. A path from one cell to another is considered shortest if and only if it contains the minimum possible number of cells among all paths connecting those two cells. Two paths are considered different if and only if there exists at least one position where the corresponding cells of the two paths are not the same.

Because you are in a hurry to watch a football match after the mission, you need to calculate the minimum number of laser shots you need to fire and the number of distinct shortest paths from the queen's chamber back to your escape cell. As the answers can be very large, output them modulo $$$(10^9 + 7)$$$.

Input

The first line contains a single integer $$$t \: (1 \leq t \leq 10^5)$$$ — the number of test cases.

Each test case consists of a single line containing two space-separated integers $$$n \: (2 \le n \le 10^6)$$$ and $$$k \: (1 \le k \le 3n(n + 1))$$$ — the number of outer layers and the escape cell.

Output

For each test case, output two space-separated integers in a line — the minimum number of laser shots you need to fire modulo $$$(10^9+7)$$$ and the number of different shortest paths from the queen's chamber to the escape cell modulo $$$(10^9+7)$$$.

Example
Input
3
2 9
4 20
1000000 3000000000000
Output
12 1
36 3
781301591 1000000
Note

In the first test case, you can kill all the guards in 12 laser shots by directing them at equal angular intervals of $$$30^\circ$$$. It can be proven that this is the minimum number of shots required. The shortest path to the escape cell is $$$0 \to 6 \to 9$$$.

The beehive of the second test case is illustrated in the statement. The three distinct shortest paths are $$$0 \to 1 \to 7 \to 20$$$, $$$0 \to 1 \to 18 \to 20$$$, and $$$0 \to 2 \to 18 \to 20$$$.