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$.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics


Solutions:
primes = [0] * (10 ** 6 + 3)
primes[0] = 1
primes[1] = 1
for p in range(2, len(primes)):
	if primes[p] == 0:
		for j in range(2, len(primes)):
			k = j * p
			if k >= len(primes):
				break
			primes[k] = 1
P = [x for x in range(len(primes)) if primes[x] == 0]

def find_factorial_factor(N):
	dic = {}
	for p in P:
		if p > 10 ** 6:
			break
		if p > N:
			break
		temp = p
		count = 0
		while temp <= N:
			count += N // temp
			temp *= p
		dic[p] = count
	return dic

def find_factor(N):
	dic = {}
	for p in P:
		if N % p == 0:
			dic[p] = 1
		if p > 10 ** 6 + 1:
			break
	return dic

def find_ans(N, K):
	prime_K = find_factor(K)
	prime_N = find_factorial_factor(N)
	prime_want = [p for p in prime_N if p not in prime_K]
	ans = [(p, prime_N[p]) for p in prime_want]
	true_ans = 1
	MOD = 10 ** 9 + 7
	for (p, exp) in ans:
		true_ans *= pow(p, exp, MOD)
		true_ans %= MOD
	return true_ans
for _ in range(int(input())):
	(N, K) = list(map(int, input().strip().split()))
	print(find_ans(N, K))


import math

def m(n, i):
	d = 0
	while n > 0:
		d += n // i
		n = n // i
	p = 1
	while d > 1:
		if d % 2 == 1:
			p *= i
		i *= i
		d //= 2
		i %= 1000000007
	return i * p % 1000000007
t = int(input())
import math
for _ in range(t):
	(n, k) = map(int, input().split())
	s = 1
	a = [True] * (n + 1)
	for i in range(2, n + 1):
		if a[i] == True and math.gcd(k, i) == 1:
			if a[i] == True:
				s *= m(n, i)
				s %= 1000000007
				for j in range(i, n + 1, i):
					a[j] = False
	print(s)


MOD = 10 ** 9 + 7
primes = [2, 3, 5, 7, 11]
p2 = [4, 9, 25, 49, 121]
act = 11
while act < 1000009:
	act += 2
	i = 1
	while p2[i] <= act and act % primes[i] != 0:
		i += 1
	if p2[i] > act:
		primes.append(act)
		p2.append(act ** 2)
pass
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	res = 1
	for p in primes:
		if p > N:
			break
		if K % p != 0:
			div = 1
			while div * p <= N:
				div *= p
				for i in range(N // div):
					res = res * p % MOD
	print(res)