미로 통행량

사장이 걸어서 통과하는 미로를 만드는 일을 맡겼고, 당신은 여러 설계안을 검토하고 있다. 하나를 확정하기 전에 각 설계에서 사람이 얼마나 빨리 드나들 수 있는지 알아 두려 한다. 사장의 관심사는 이 사업으로 돈을 버는 것이고, 사람이 빨리 통과할수록 더 많은 손님을 받을 수 있다.

미로는 번호가 붙은 방과 방을 잇는 통로로 이루어진다. 미로의 입구는 번호가 가장 작은 방 하나뿐이고, 출구는 번호가 가장 큰 방 하나뿐이다.

통로마다 한 번에 지나갈 수 있는 인원에 제한이 있다. 번호가 $x$인 방과 $y$인 방의 최대공약수가 $1$보다 크면 두 방 사이에 통로가 있다. 그 최대공약수를 $p$라고 하면 $x$에서 $y$로 1분에 $p$명이 걸어갈 수 있다. 동시에 $y$에서 $x$로도 1분에 $p$명이 걸어갈 수 있다. 입구와 출구, 그리고 각 방은 한 번에 몇 명이 지나가든 감당한다. 사람들은 미로를 최대한 빨리 통과하려 하므로 방에 머무르지 않는다.

입력은 미로 하나를 설명한다. 첫째 줄에 미로에 있는 방의 개수 $n$이 주어진다. ($2 \le n \le 1000$)

다음 $n$개의 줄에 방 번호가 한 줄에 하나씩 주어진다. 방 번호는 서로 다르고, 각각 $2$ 이상 $2 \times 10^9$ 이하이다.

사람이 나가는 속도가 들어오는 속도와 같다고 할 때, 1분에 미로로 들어갈 수 있는 최대 인원을 출력한다. 1분에 $10^9$명을 넘게 받는 미로는 입력으로 주어지지 않는다.