5572: 最大公约数（gcd）
[Creator : ]
Description
给定 $n$ 个正整数，$a_1,\ a_2,\ \cdots,\ a_n$，求最少删去几个数，使得删去后这些数的最大公约数比原先的所有数的最大公约数大。
Input
第一行一个整数 $n$，
第二行 $n$ 个正整数，$a_1,\ a_2,\ \cdots,\ a_n$。
第二行 $n$ 个正整数，$a_1,\ a_2,\ \cdots,\ a_n$。
Output
一个数，表示最少删去的个数，若无论怎么删都不会比原来的大，输出 $-1$。
Constraints
对于 $30\%$ 的数据，$n \leq 15$；
对于 $50\%$ 的数据，$n,\ a_i \leq 1000$；
对于 $100\%$ 的数据，$n \leq 300,000$，$a_i \leq 1.5*10^7$。
对于 $50\%$ 的数据，$n,\ a_i \leq 1000$；
对于 $100\%$ 的数据，$n \leq 300,000$，$a_i \leq 1.5*10^7$。
Sample 1 Input
3
1 2 4
Sample 1 Output
1
删去 $1$ 这个数，最大公约数从 $1$ 变到 $2$。
Sample 2 Input
4
6 9 15 30
Sample 2 Output
2
删去 $6,\ 9$，最大公约数从 $3$ 变到 $15$。
Sample 3 Input
3
1 1 1
Sample 3 Output
-1
HINT
题目来源：2018年余姚市小学生程序设计竞赛复赛。