题目内容

在一套传感指标采集系统中，共有 $n$ 个节点，每个节点都会产生一个正整数指标。为了让所有节点的数据具有更明显的共同特征，希望这些指标能够共享一个大于 $1$ 的公因数。

给定长度为 $n$ 的正整数数组

要求最终满足

你可以执行任意次调整操作。每次选择一个下标 $i$，将 $v_i$ 修改为任意正整数。

请计算，为满足上述条件，至少需要修改多少个位置。

输入描述

第一行读入一个整数 $n\ (1\le n\le 120000)$，表示指标的数量。

第二行读入 $n$ 个整数 $v_1,v_2,\ldots,v_n\ (1\le v_i\le 900000)$，表示每个位置当前的指标值。

输出描述

输出一个非负整数，表示使整个数组的最大公约数大于 $1$ 所需的最少修改次数。

样例1

输入

4
8 12 20 28

输出

0

说明

当前数组中所有元素都能被 $4$ 整除，因此

已经满足要求，无需修改任何位置。

样例2

输入

4
1 1 1 1

输出

4

说明

整数 $1$ 不含任何大于 $1$ 的因数，因此不存在一个大于 $1$ 的整数能够整除当前的任意一个元素。

所以四个位置都必须进行修改，最少需要 $4$ 次操作。

样例3

输入

6
14 21 25 35 9 6

输出

3

说明

例如选择质数 $3$ 作为所有元素最终共有的因数。

当前能够被 $3$ 整除的元素为 $21,9,6$，共 $3$ 个，因此只需要将剩余的 $14,25,35$ 修改为 $3$ 的倍数，共进行 $3$ 次操作。

选择质数 $7$ 时，同样只有 $14,21,35$ 三个元素可以保留；其他质数能够直接整除的元素不会更多，因此最少需要修改 $3$ 个位置。