수 고르기

친구들과 자주 하는 게임에서 계속 지고 있다. 이 게임은 마지막에 손에 가장 큰 수를 들고 있는 사람이 이긴다. 게임을 시작할 때 탁자 위에는 서로 다른 수가 놓여 있다. 자기 차례에는 탁자 위의 수 하나를 골라 손에 든다. 다만 손에 든 수를 버려야 하는 경우가 생긴다.

게임이 진행되는 동안 각 수는 탁자 위, 어느 참가자의 손, 버림 더미 중 한 곳에 있다. 참가자가 탁자에서 수 $x$를 고르면 $x$를 탁자 위에 없는 모든 수 $y$와 비교한다. 여기에는 다른 참가자의 손, 자신의 손, 버림 더미에 있는 수가 모두 포함된다. $x$와 $y$의 공약수 중 $1$보다 큰 것이 있으면 두 수를 모두 버림 더미로 옮기고, 이미 버림 더미에 있던 수는 그대로 둔다. 탁자 위의 수를 모두 고르면 게임이 끝난다.

탁자 위에 놓인 수가 주어질 때, 고르면 반드시 이기는 수를 구하라.

입력의 각 줄은 게임 하나의 시작 상태를 나타낸다. 줄의 맨 앞에 $1 \le n \le 1000$이 오고, 이어서 서로 다른 양의 정수 $n$개가 주어진다. 각 정수는 $2$ 이상 $2 \times 10^9$ 이하이며, 게임을 시작할 때 탁자 위에 놓인 수다. 게임은 최대 $1000$개 주어지고, 입력은 파일 끝에서 끝난다.

각 게임마다 고르면 반드시 이기는 수 $x$를 한 줄에 하나씩 출력한다. 주어지는 각 게임에는 이런 수가 정확히 하나 있다.