Background

椒江区赛的第三题《逃脱食人族》，也是求最大公约数的问题，R老师看了之后觉得题目太水了！！！！才50个数，这种数据范围也配放在第三题？光写个GCD谁都会好不好！

所以R老师发动了他的数论思维，出了一道读起来很简单，但是很解决起来复杂一些的GCD相关问题。问题如下：

给定$n$个正整数，$a_1,a_2,…,a_n$,求最少删去几个数，使得删去后这些数的最大公约数比原先的所有数的最大公约数大。

怎么样，题目意思是不是很好理解！

Input

第一行一个整数$n$，第二行$n$个正整数，$a_1,a_2,…,a_n$。

Output

一个数，表示最少删去的个数，若无论怎么删都不会比原来的大，输出-1。

Samples

3
1 2 4

1

4
6 9 15 30

2

Limitation

【样例 $1$ 解释】

删去 $1$ 这个数，最大公约数从 $1$ 变到 $2$。

【样例 $2$ 解释】

删去 $6、9$，最大公约数从 $3$ 变到 $15$

【数据范围】

对于30%的数据，$n<=15$

对于50%的数据，$n,a_i<=1000$

对于100%的数据，$n<=300,000，a_i<=1.5*10^7$