说明

你有一个魔法集合，初始包含 $n$ 个互不相同的整数。你发现这些数字可以通过分解为因数来产生能量。每一步中，你可以从集合中任意选择一个大于 $1$ 的数字，将其移除，并插入它的一个因数。你插入的因数不能等于原数字。此外，由于魔法集合的不稳定性，你的操作必须保证集合中的数字始终保持互不相同。

每次操作产生一个单位的能量，你的目标是通过执行尽可能多的操作来最大化总能量。给定集合中的初始数字，确定可以产生的最大能量，即可以执行的最大操作次数。

输入格式

• 第一行包含一个整数 $n$（$1 \le n \le 300$），表示初始集合中整数的个数。
• 第二行包含 $n$ 个互不相同的整数 $a_i$（$1 \le a_i \le 10^9$），表示初始集合中的数字。

输出格式

输出一个整数，表示可以产生的最大能量，即可以执行的最大操作次数。

3
2 4 6

3

6
2 3 5 6 10 12

3

提示

翻译由 DeepSeek V3 完成