Professor KCM's Question

Professor KCM is famous for the vicious questions he asks in class. When a student he calls on cannot answer, or answers wrong, C and D grades rain down on that student. Today he watched the class with a hawk's eye while deciding what to ask, and a truly vicious question came to him.

He wiped every line of the lecture off the blackboard and started scribbling natural numbers all over it. Then he shouted at the class.

"All right, the game starts now. Work together and find the answer to my question. If the answer you find together is correct, I will never ask a question in class again. If it is wrong, F grades rain down on your transcripts!"

The students thought this was their last hope, so they listened closely.

"I just wrote a pile of natural numbers on the board, right? You may apply the following operation to them as many times as you like. Pick two numbers $x$ and $y$ on the board, erase them, and write $\gcd(x, y)$ and $\operatorname{lcm}(x, y)$ in their place. Repeat the operation and the numbers on the board keep changing. When the moment feels right, pick the largest number still on the board and hand it to me. What is the largest result you can produce this way? That is my question... ha ha..."

doju, who happened to be in that class, wanted to run out of the room, but students from Professor KCM's lab came down and locked the door, so escape was impossible. Now that the question cannot be avoided, doju is asking you for help. Find the answer to the professor's question so doju can escape.

The first line contains the number of test cases $T$.

Each test case consists of two lines. The first line contains the count $N$ ($1 \le N \le 10^6$) of natural numbers the professor wrote. The second line contains those $N$ natural numbers, separated by spaces. Each number is between 1 and 1,000.

The sum of $N$ over all test cases does not exceed 2,000,000.

For each test case, print the answer to the professor's question on its own line. The answer can grow very large, so print only its remainder modulo 1,000,000,007.

In the first example the operations can go like this. Pick 20 and 3 first, and the two numbers turn into 1 and 60. Then pick 60 and 8, and those two turn into 4 and 120. Hand in 120 at that point, which is the largest value that can be produced.