KCM 교수의 질문

KCM 교수는 수업 시간에 악랄한 질문을 던지기로 유명하다. 질문을 받은 학생이 대답하지 못하거나 틀린 답을 말하면 그 학생의 성적에 C와 D가 빗발친다. 오늘도 매의 눈으로 학생들을 살피며 무슨 질문을 할지 고민하던 교수는 갑자기 아주 악랄한 질문 하나를 떠올렸다.

교수는 칠판에 적혀 있던 수업 내용을 모두 지우고 자연수를 마구 적기 시작했다. 그러고는 학생들을 향해 이렇게 외쳤다.

"자, 이제 게임을 시작하지. 여러분은 힘을 모아 내가 내는 질문의 답을 구해야 할 거야. 힘을 모아 구한 답이 맞다면 앞으로 수업 시간에 질문을 하지 않겠다. 하지만 틀린다면 여러분의 학점에 F가 빗발친다!"

학생들은 이번이 마지막 희망이라 생각하고 교수의 말에 귀를 기울였다.

"내가 방금 칠판에 자연수를 적었지? 여러분은 여기에 다음 연산을 마음대로 여러 번 수행할 수 있어. 칠판에 적힌 두 수 $x$와 $y$를 골라 지운 다음, 그 자리에 $\gcd(x, y)$와 $\operatorname{lcm}(x, y)$를 적는 거야. 이 연산을 반복하면 칠판의 수가 계속 바뀌겠지? 그러다 적당한 때가 되면 남아 있는 수 가운데 가장 큰 수를 골라 나에게 제출해야 해. 이때 만들 수 있는 결과의 최댓값은 얼마일까? 이게 바로 내 질문이야... 하하..."

마침 그 수업을 듣고 있던 doju는 강의실에서 도주하고 싶었지만, KCM 교수의 연구실 학생이 내려와 강의실 문을 잠가버려 도주할 수 없었다. 질문을 피할 수 없게 된 doju는 여러분에게 도움을 요청했다. 교수의 질문에 답을 구해 doju가 도주하게 해주자.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에 교수가 적은 자연수의 개수 $N$($1 \le N \le 10^6$)이 주어진다. 둘째 줄에 교수가 적은 자연수 $N$개가 공백으로 구분되어 주어진다. 각 수는 1 이상 1,000 이하이다.

모든 테스트 케이스의 $N$을 더한 값은 2,000,000을 넘지 않는다.

각 테스트 케이스마다 교수의 질문에 대한 답을 한 줄씩 출력한다. 답이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지만 출력한다.

첫 번째 예제에서는 다음과 같이 연산할 수 있다. 먼저 20과 3을 고르면 두 수는 1과 60으로 바뀐다. 다음으로 60과 8을 고르면 두 수는 4와 120으로 바뀐다. 이 상태에서 120을 골라 제출하면 되고, 이 값이 만들 수 있는 최댓값이다.