Reference: Codeforces 1034A — Enlarge GCD

You are given ~n~ positive integers:

~a_1, a_2, \ldots, a_n~

You may remove some of the integers, but at least one integer must remain.

Find the minimum number of integers that must be removed so that the greatest common divisor of the remaining integers is strictly greater than the greatest common divisor of all the original integers.

Input

• The first line contains one integer ~n~.
• The second line contains ~n~ integers: ~a_1, a_2, \ldots, a_n~.

Output

• Print the minimum number of integers that must be removed.
• If it is impossible to increase the greatest common divisor, print ~-1~.

Constraints

• ~2 \le n \le 3 \times 10^5~
• ~1 \le a_i \le 1.5 \times 10^7~

Example 1

Input:

4
6 9 15 30

Output:

2