Description

小杨交给小黄一个大小为 $n$ 的序列 $a$，并让小黄执行一些操作。

在一次操作中，小黄可以选择一个特殊的正整数 $q$，$q$ 可以表示为一个质数的正整数次幂。并在序列 $a$ 中任意选择一些能被 $q$ 整除的元素，然后将序列 $a$ 中被选择的元素除以 $q$。

小黄需要用最少的操作数使得序列 $a$ 的所有数相同，如果做不到，小杨将会在小黄的寝室安装摄像头并且禁止小黄和自己之外的人玩网络游戏。

小黄不想被监视，请你告诉小黄使得序列 $a$ 的所有数相同所需的最少操作数。

Format

Input

第一行有一个整数 $n\ (1 \leq n \leq 10^5)$，表示序列 $a$ 的长度。

第二行有 $n$ 个整数 $a_1, a_2, \cdots, a_n\ (1 \leq a_i \leq 10^6)$，表示需要操作的序列。

Output

输出一个整数，表示使得序列 $a$ 的所有数相同所需的最少操作数。

Samples

4
6 12 24 48

2

Note

对于第一个样例，第一次操作选择 $q = 2$，在序列 $a$ 中选择 $[12, 48]$，操作后序列 $a$ 为 $[6, 6, 24, 24]$。

第二次操作选择 $q = 4\ (2^2)$，在序列 $a$ 中选择 $[24, 24]$，操作后序列 $a$ 为 $[6, 6, 6, 6]$，完成要求使得 $a$ 中所有数相同，最少操作次数为 $2$。

Limitation

1s, 1024KiB for each test case.