ADACON  Ada and Connections
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_{1},a_{2},a_{3},...,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 A1. 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^{5}, the number of friend who were on trip (and also the number of numbers).
The second line contains N integers 0 ≤ a_{i} ≤ 10^{6}
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
hide comments
black_shroud:
20200612 21:50:43
Last edit: 20200612 22:02:47 

hodobox:
20181231 20:28:33
@Rohit Agarwal you can add 1 to each number to make them all even and so gcd(array) = 2.


Rohit Agarwal:
20181120 15:06:25
@morass: Could you please explain the last testcase? Why the answer is 5? Last edit: 20181120 16:36:41 

Rohit Agarwal:
20181119 15:45:39
Getting WA, any testcases guys? 

hyperion101010:
20180905 16:37:21
is there a solution i am starting to get disinterested i got tle with java following @manya_cod4 tip but i think approach is different :(


mack_156890:
20180904 19:09:22
hey can anyone tell me what is there complexity?


manya_cod4:
20171218 13:58:32
@morass what is the expected time complexity of this problem.? mine is n * (number of prime numbers upto largest number )


feodorv:
20170623 02:00:27
I think it's my fault in misunderstanding the problem))) I was bound to guess that the solution must exist in any case. Meanwhile you could set one more problem (say ADACON0) with restricted rules for changing Ai ;) 

morass:
20170623 01:35:08
@feodorv: Even though it you passed a few testcases :P Anyway sorry for unclear statement :/ 

feodorv:
20170623 01:29:46
Oh, so i am solving other problem)))

Added by:  Morass 
Date:  20170622 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 