Ada the Ladybug was on a trip with her friends. They each bought a souvenir there. As all of them are mathematicians, everybody bought a number. They want to modify the numbers to have some connection between each other. They have decided to modify the numbers sou they would have their GCD greater than 1 ( gcd(a₁,a₂,a₃,...,a_N)>1). Anyway it is not easy to change a number - the only thing they can do is to go to a proffesor in mathematics, which could forge a number A into number A+1 or A-1. As this operation is not cheap, they want to minimize number of such operations. A number might be forged any number of times.

NOTE: gcd(a,0)==a (so gcd of two 0 is also 0)

Input

The first line contains an integer 1 ≤ N ≤ 3*10⁵, the number of friend who were on trip (and also the number of numbers).

The second line contains N integers 0 ≤ a_i ≤ 10⁶

Output

Print a single line with minimum number of operations to make a connection between all numbers.

Example Input

5
3 9 7 6 31

Example Output

2

Example Input 2

9
3 4 5 7 8 9 11 12 13

Example Output 2

6

Example Input 3

5
7 7 11 17 1

Example Output 3

5