시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 683 141 122 30.348%

문제

KCM 교수는 수업 시간에 악랄한 질문을 하기로 유명하다. 어떤 학생에게 질문을 던졌을 때 대답하지 못하거나 틀린 답을 하면 그 학생의 성적에는 C, D가 빗발치게 된다. 오늘도 학생들을 매의 눈으로 바라보며 어떤 질문을 할지 고민 중이던 그는 갑자기 엄청나게 악랄한 질문을 떠올렸다.

우선 칠판에 수업 중이던 내용을 다 지우고는 임의의 자연수들을 미친듯이 막 적어대기 시작했다. 그러고는 학생들을 향해 이렇게 외쳤다.

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

학생들은 이번이 마지막 희망이라 생각하고 교수의 말을 주의깊게 들었다.

“내가 지금 칠판에 자연수들을 막 적었지? 여러분은 여기에 특정한 연산을 마음대로 여러번 수행할 수 있어. 이 연산이 뭐냐하면 특정한 두 숫자 x, y 를 고른 다음에 그 둘을 지워. 그리고 그 자리에 gcd(x, y)lcm(x, y)를 적는거야. 이 연산을 반복하면 칠판에 적혀있는 숫자들이 막 바뀌겠지? 그러고나서 적당한 때가 되면 여러분은 그 때 남아있던 숫자들 중에 가장 큰 숫자를 골라 나에게 제출해야 해. 이 때 만들 수 있는 결과의 최대값은 무엇일까? 바로 이것이 질문이야... 하하...”

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

입력

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

각 테스트 케이스는 두 줄로 구성되어 있다. 첫 번째 줄에 교수가 적은 자연수의 개수 N(1 ≤ N ≤ 1, 000, 000) 이 주어진다. 두 번째 줄에 교수가 적은 자연수 N 개가 공백으로 구분되어 주어진다. 각 수는 1이상 1, 000 이하이다.

모든 테스트 케이스에서 N 의 합이 2, 000, 000을 넘지 않는다.

출력

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

예제 입력

1
5
1 30 3 20 8

예제 출력

120

힌트

첫번째로 20과 3을 고른다. 연산을 수행하면 두 수는 1과 60 으로 바뀐다.

두번째로 60과 8을 고른다. 연산을 수행하면 두 수는 4 와 120 으로 바뀐다.

이 상태에서 120을 골라 제출하면 된다. 이것이 만들 수 있는 수 중에 최대값이다.