You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面描述

神秘的东方大陆有一个魔法挑战，在魔法挑战中，有一个含有 $N$ 个正整数的序列 $A_1,A_2,\ldots,A_N$ 。

你作为最著名的魔法大师，欣然前往接受了挑战，在挑战中，你需要把****整个序列的所有数字变得完全一致，

所幸你可以使用魔法来完成：

• 在一次魔法操作中，你可以选择序列的一个下标 $i$ ，然后任选一个能整除 $A_i$ 的魔法参数 $k$ ，把 $A_i$ 变成 $A_i/k$ 。
• 由于太多的施法会使你精疲力竭，所以请你找出最少的施法次数，使得序列中的数字完全一致，可以证明挑战是必定有解的。

输入格式

第一行输入一个正整数 $N$，表示序列长度。

第二行输入 $N$ 个正整数 $A_1, A_2, \ldots, A_N$，序列中的元素。

输出格式

输出一行一个整数，表示最少的施法次数

输入输出样例

input1

4
2 4 8 6

output1

3

input2

4
3 5 7 11

output2

4

说明 / 提示

样例说明

第一组数据，魔法操作如下

• 选择下标 $2$ ，$k$ 为 $2$ ，$A_2 := A_2/2$
• 选择下标 $3$ ，$k$ 为 $4$ ，$A_3 := A_3/4$
• 选择下标 $4$ ，$k$ 为 $3$ ，$A_4 := A_4/3$

最终序列中全部数字都为 $2$ ，施法次数为 $3$

第二组数据，把每个元素都变为 $1$ ，总共需要 $4$ 次操作。

数据范围

• 对于 $50\%$ 的数据，$1\le N \le 10^3, 1\le A_i \le N$
• 对于 $100\%$ 的数据，$1\le N \le 2\times 10^5, 1\le A_i \le N$