You are given an array of positive integers. You can do the following operation any number of times (possibly zero).
First, choose two integers and and
Then, choose a positive proper divisor of
Finally, replace with and with .
You have to maximize the Least Common Multiple (LCM) of the array. Since the LCM of the array can be enormous, print it module .
Least Common Multiple of an array 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, are proper divisors of , but itself is not.
Each test contains multiple test cases. The first line contains a single integer — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer — the size of the array.
The second line contains space-separated integers — the elements of the array.
It is guaranteed that the sum of over all test cases does not exceed .
Print a single number — the maximum possible LCM of the array modulo .
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:
In the second case, no operation is possible. So, the maximum LCM is the LCM of the original array.