Maze movement

Your boss gave you the task of designing a walk-through maze, and you are comparing several layouts. Before you settle on one, you want to know how quickly people can move in and out of each layout. Your boss wants this venture to make money, and the faster people move through, the more paying customers you can handle.

A maze is a set of numbered rooms and the passages connecting them. The only entrance is the lowest-numbered room and the only exit is the highest-numbered room.

Each passage limits how many people can pass through at a time. For rooms numbered $x$ and $y$, a passage joins them whenever the greatest common divisor of $x$ and $y$ is larger than $1$. Call that divisor $p$. Then $p$ people per minute can walk from $x$ to $y$, and at the same time $p$ people per minute can walk from $y$ to $x$. The entrance, the exit, and every room handle any number of people at a time. People want to get through the maze as quickly as possible, so they never wait in a room.

The input describes a single maze. The first line holds the number of rooms $n$. ($2 \le n \le 1000$)

Each of the next $n$ lines holds one room number. The room numbers are distinct, and each one is between $2$ and $2 \times 10^9$.

Print the largest number of people per minute that can enter the maze, assuming people leave the maze at the same rate they enter it. No maze given in the input supports more than $10^9$ people entering per minute.