Least Complicated Mind

You are given an array $A$ of $N$ positive integers. You can do the following operation any number of times (possibly zero).

• First, choose two integers $A_i$ and $A_j$ $(1 \leq i, j \leq N$ and $i \neq j)$

• Then, choose a positive proper divisor $X$ of $A_i$ $(1 \leq X < A_i)$

• Finally, replace $A_i$ with $A_i / X$ and $A_j$ with $A_j \times X$.

You have to maximize the Least Common Multiple (LCM) of the array. Since the LCM of the array can be enormous, print it module $10^9 + 7$.

Least Common Multiple of an array $A$ is the minimum positive integer that is divisible by every elements of that array.

A proper divisor is a positive divisor of a number, excluding itself. For example, $(1, 2, 4, 5, 10)$ are proper divisors of $20$, but $20$ itself is not.

Input

Each test contains multiple test cases. The first line contains a single integer $T$ $(1 ≤ T ≤ 4 \times 10^4)$— the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $N$ $(1≤ N ≤ 5 \times {10^5})$— the size of the array.

The second line contains $N$ space-separated integers $A_1,A_2,…,A_N$ $(1≤ A_i ≤ 10^6)$ — the elements of the array.

It is guaranteed that the sum of $N$ over all test cases does not exceed $5\times10^5$.

Output

Print a single number — the maximum possible LCM of the array modulo $1000000007 (10^9 + 7)$.

Sample

Input	Output
4 3 60 45 77 2 2 7 2 15 18 2 196608 84035	207900 14 270 521953168
In the first case, one possible way to get the maximum LCM is: Choose $A_1$ and $A_3$. Divide $A_1$ by $15$ and Multiply $A_3$ by $15$. In the second case, no operation is possible. So, the maximum LCM is the LCM of the original array.