Description

小A有一个包含 N 个正整数的序列 A = {A1, A2, ..., AN}。小A每次可以花费 1 个金币执行以下任意一种操作：

1. 选择序列中一个正整数 Ai (1 <= i <= N)，将 Ai 变为 Ai * P，P 为任意质数；

2. 选择序列中一个正整数 Ai (1 <= i <= N)，将 Ai 变为 Ai / P，P 为任意质数，要求 Ai 能整除 P。

小A想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。

Input Format

第一行一个正整数 N，含义如题面所示。

第二行包含 N 个正整数 A1, A2, ..., AN，代表序列 A。

Output Format

输出一行，代表最少需要花费的金币数量。

5
10 6 35 105 42

8

Hint

对于 60% 的测试点，保证 1 <= N, Ai <= 100。

对于所有测试点，保证 1 <= N, Ai <= 10^5。

Source