Least Complicated Mind

Ahasan_1999 CUET CSE Fest 2022 - Inte...
Limits 1s, 512 MB

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

  • First, choose two integers AiA_i and AjA_j (1i,jN(1 \leq i, j \leq N and ij)i \neq j)

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

  • Finally, replace AiA_i with Ai/XA_i / X and AjA_j with Aj×XA_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 109+710^9 + 7.

Least Common Multiple of an array AA 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)(1, 2, 4, 5, 10) are proper divisors of 2020, but 2020 itself is not.

Input

Each test contains multiple test cases. The first line contains a single integer TT (1T4×104)(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 NN (1N5×105)(1≤ N ≤ 5 \times {10^5})— the size of the array.

The second line contains NN space-separated integers A1,A2,,ANA_1,A_2,…,A_N (1Ai106)(1≤ A_i ≤ 10^6) — the elements of the array.

It is guaranteed that the sum of NN over all test cases does not exceed 5×1055\times10^5.

Output

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

Sample

InputOutput
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 A1A_1 and A3A_3. Divide A1A_1 by 1515 and Multiply A3A_3 by 1515.

In the second case, no operation is possible. So, the maximum LCM is the LCM of the original array.


Submit

Login to submit.

Statistics

39% Solution Ratio
adnan_tokyEarliest, 1M ago
ash_98Fastest, 0.1s
adnan_tokyLightest, 7.1 MB
ash_98Shortest, 1606B
Toph uses cookies. By continuing you agree to our Cookie Policy.