题目描述

小明现在在进行一个数字游戏。在游戏中，给定一个初始数字 $n$，可以对数字做以下操作任意次：

• 选择一个形如 $x = p^k$ 的数字，其中 $p$ 是一个质数，$k \geq 1$，且 $x$ 是当前 $n$ 的因数；
• 将 $n$ 更新为 $n / x$；
• 每次选取的 $x$ 必须互不相同。

现在小明想知道，最多可以进行多少次这样的操作？

换句话说，我们要从 $n$ 的质因数分解中，选出若干个不同的质数幂（即形式为 $p^k, k\geq1$），使得它们的乘积能整除原始 $n$，并且个数尽可能多。

输入格式

输入共一行，包含一个整数 $n$（$2 \leq n \leq 5 \times 10^7$），表示数字的初始值。

输出格式

输出一个整数，表示游戏过程中最多可以进行多少次操作。

500

3

样例解释

可以将 500 先除以 5（即 $5^1$），再除以 25（即 $5^2$），再除以 2（即 $2^1$），共执行 3 次操作。

注意：虽然 5 和 25 都是基于质数 5 的幂，但它们是不同的数值（$5^1 \ne 5^2$），因此允许同时选；而不能再选另一个 $5^3=125$，因为 $500 / (5 \times 25 \times 2) = 2$，已无剩余因子支持更大的 5 的幂。