Coprime Neighbors

Time limit2sMemory limit512 MB

Summary

Given a set of up to 50 distinct integers, insert the fewest new distinct positive integers so that consecutive values in sorted order are coprime.

Level: Hard8 of 10
Topics: Math, Number theory, Greedy, Dynamic programming
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Hint

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

Examples3

Example 1
Input
```
4
2200 42 2184 17
```
Expected output
```
3
```
Example 2
Input
```
5
13 1 6 20 33
```
Expected output
```
0
```
Example 3
Input
```
2
7 42
```
Expected output
```
1
```