题目内容

物流中心收到 $n$ 个货箱，第 $i$ 个货箱上标有正整数 $a_i$。调度系统要求这些编号存在一个大于 $1$ 的公共因子，即存在整数 $d>1$，使得所有 $a_i$ 都能被 $d$ 整除。等价地，需要满足 $\gcd(a_1,a_2,\ldots,a_n)>1$。

在正式入库前，可以对任意货箱重新打印编号。每次操作选择一个货箱，将其编号改为任意正整数。请计算最少需要修改多少个货箱的编号，才能使全部编号的最大公约数大于 $1$。

本题中，货箱数量 $n$ 不超过 120000，每个编号 $a_i$ 不超过 900000，且均为正整数。

输入描述

第一行包含一个整数 $n$（$1 \le n \le 120000$），表示货箱数量。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 900000$），表示每个货箱当前的编号。

输出描述

输出一个非负整数，表示需要修改的最少货箱数量。

样例1

输入

4
2 3 4 5

输出

2

说明

选择质数 $2$ 作为公共因子时，数组中的 2 和 4 能被 $2$ 整除，共可保留 2 个货箱。质数 $3$ 只能保留 1 个，质数 $5$ 也只能保留 1 个。因此最多保留 2 个货箱，最少需要修改 $4-2=2$ 个货箱，例如把 3 和 5 都修改为 2 的倍数。

样例2

输入

3
7 7 7

输出

0

说明

所有编号均为 7，已经都能被质数 $7$ 整除，因此整个数组的最大公约数大于 1，满足要求，不需要修改任何货箱。

样例3

输入

3
1 1 1

输出

3

说明

元素 1 不能被任何大于 1 的整数整除，所以对任意质数 $p$，能被 $p$ 整除的数量都是 0。没有货箱可以直接保留，全部 3 个货箱都需要修改，答案为 $3$。

样例4

输入

3
6 10 15

输出

1

说明

选择质数 $2$ 时，6 和 10 能被 $2$ 整除；选择质数 $3$ 时，6 和 15 能被 $3$ 整除；选择质数 $5$ 时，10 和 15 能被 $5$ 整除。最多可以保留 2 个货箱，因此最少需要修改 $3-2=1$ 个货箱。例如保留 6 和 10，把 15 修改为 2 的倍数即可。