Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chef likes sequences of integers and in particular, he likes arithmetic progressions.

There are two integers $N$ and $K$. Chef wants to choose a starting positive integer $A$, create the sequence $(A, A+K, A + 2 \cdot K, \ldots, A + (N-1) \cdot K)$ and compute the product of all elements of this sequence; let's denote this product by $X$. For example, if $N=3$ and $K=2$, then Chef can create the sequence $(4,6,8)$, for which $X=192$.

Find the largest integer that divides $X$ regardless of the value of $A$ that Chef chooses. Since the answer can be large, compute it modulo $1,000,000,007$ ($10^{9} + 7$).

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two space-separated integers $N$ and $K$.

------ Output ------
For each test case, print a single line containing one integer — the largest number that always divides $X$, modulo $1,000,000,007$.

------ Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{6}$
$1 ≤ K ≤ 10^{18}$

----- Sample Input 1 ------
2

2 2

3 1
----- Sample Output 1 ------
1

6
----- explanation 1 ------
Example case 1: If Chef chooses $A=1$, the sequence he creates is $(1,3)$ and then, $X$ is $3$, and if he chooses $A=2$, the sequence is $(2,4)$ and $X$ is $8$. We can see that the largest integer that divides them both is $1$.

Example case 2: The product of any $3$ consecutive integers is always divisible by $6$.

见题面

见题面