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