Coprime Neighbors

A set $A$ of $N$ distinct positive integers is given. Youngsun wants to put more positive integers into the set. After she is done, sort every number in the set in increasing order: the greatest common divisor of two neighboring numbers must not exceed 1. In other words, neighboring numbers in the sorted order must be coprime.

Write a program that finds the minimum count of numbers she has to put in. Every new number is a positive integer, and because $A$ is a set, a new number cannot equal a number that is already in it.

The first line contains $N$. ($1 \le N \le 50$)

The second line contains the $N$ numbers of the set, separated by spaces. Each number is a natural number not greater than 100,000, and all of them are distinct. They are not necessarily given in sorted order.

Print the minimum count of numbers that must be put in on the first line.

One gap can need two new numbers. No integer strictly between 2184 and 2200 is coprime to both of them.