题目背景

小 E 在玩一个数字游戏。

题目描述

小 E 有 $n$ 个正整数 $a_1,a_2,\dots,a_n$。他可以进行以下操作任意次：

选择一个数 $q$，和一个集合 $S=\{d_1,d_2,\dots,d_m\}$，使得 $a_{d_1},a_{d_2},\dots,a_{d_m}$ 能被 $q$ 整除，并将 $a_{d_1},a_{d_2},\dots,a_{d_m}$ 除以 $q$。

• $q$ 要满足可以写成 $p^z$ 的形式，其中 $p$ 为质数，$z$ 为正整数。

求最少需要进行多少次操作才能将这些数变为相等的数。

输入格式

第一行，一个整数 $n$。

第二行，$n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出一个整数表示答案。

5
12 30 48 36 18

4

10
72 81 27 90 45 45 27 99 45 18

6

4
1 2 4 8

2

提示

「样例 1 说明」

一开始的序列为 12 30 48 36 18。
选择 $S=\{4,5\},p=3$，操作后变为 12 30 48 12 6。
选择 $S=\{1,3,4\},p=2$，操作后变为 6 30 24 6 6。
选择 $S=\{2\},p=5$，操作后变为 6 6 24 6 6。
选择 $S=\{3\},p=2^2=4$，操作后变为 6 6 6 6 6。
共 4 次操作，方法不唯一。

「数据范围与约定」

本题使用捆绑测试。

对于 $100\%$ 的数据，有 $1\leq n\leq 10^5$，$1\leq a_i\leq 10^6$。

对于所有测试点，时间限制 1s，空间限制 128MB。

「来源」

Sweet Round 03 B。
idea & solution：ET2006 & Alex_Wei。