D. Toward Divisibility
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers, you can do this operation at most once:

  • Choose a subset of elements of the array and an integer and add this integer to all elements in this subset. In other words, choose a subset $$$S \subseteq \{ 1, 2, ..., n \}$$$ and an integer $$$X$$$ and set $$$a_i=a_i+X$$$ for each $$$i \in S$$$.

Print the minimum size of a subset you can choose such that after performing the operation, the GCD (Greatest Common Divisor) of all elements of the array is greater than one. If the GCD is already greater than one without performing the operation, print $$$0$$$.

Input

The first line of the input contains a single integer $$$n \: ( 1 \le n \le 10^6)$$$ — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_i (1 \le a_i \le 10^9)$$$ — the elements of the array $$$a$$$.

Output

Print a single integer — the minimum size of the chosen subset or $$$0$$$ if the GCD is already greater than one.

Example
Input
5
1 2 3 4 5
Output
3