B. Walkability
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Karpsburg is a neighborhood made of $$$n$$$ houses, each of which has a house number $$$a_i$$$. For every pair of houses, there is a bidirectional road between them. For all $$$1\le i \lt j\le n$$$, there is a bidirectional sidewalk between houses $$$i$$$ and $$$j$$$ if and only if there exists a positive integer $$$k \gt 1$$$ such that $$$a_i\equiv a_j \pmod k$$$. Roads can only be traversed by car, and sidewalks can only be traversed by walking.

Magikarp wants to go trick-or-treating in Karpsburg, but he does not want to drive very much. Magikarp starts at a house of his choice. From here, he may either walk along a sidewalk or drive along a road to another house.

What is the minimum number of times that Magikarp must drive for him to visit every house exactly once?

Input

The first line of input contains $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of houses.

The second line of input contains $$$n$$$ space-seperated integers, $$$a_1, a_2, \ldots ,a_n$$$ ($$$1\le a_i\le 10^9$$$) — the house numbers of the $$$n$$$ houses. It is not guaranteed that all house numbers are distinct.

Output

Output a single integer, the minimum number of times that Magikarp must drive.

Examples
Input
5
1 3 4 8 9
Output
0
Input
2
6 7
Output
1