Iroha 和 Kaguya 最近迷上了一种基于整数的数学游戏。

最初，她们共有一个正整数 $n$。两人轮流进行操作；一轮定义为 Iroha 和 Kaguya 各完成一次操作。在每一轮中：

1. Iroha 先手：她必须选择一个非负整数 $x$ ($0\le x<n$)，并将当前的 $n$ 替换为 $n+x$。

2. Kaguya 后手：她必须选择一个能整除当前 $n$ 的质数 $p$（即 $p\mid n$），并将当前的 $n$ 替换为 $\frac{n}{p}$。

上述操作不断重复。如果任意一轮结束后 $n=1$，游戏立即结束。

游戏中，Iroha 希望最大化游戏进行的总轮数，而 Kaguya 希望最小化总轮数。假设两人都完全理性且采用最优策略，请确定游戏最终会持续的总轮数。

输入格式

第一行包含一个整数 $n$ ($1\le n\le10^{18}$)，表示游戏的初始数。

输出格式

输出一行，包含一个整数，表示双方都采用最优策略时游戏持续的总轮数。

样例

输入格式 1

1

输出格式 1

0

输入格式 2

9

输出格式 2

4

输入格式 3

16

输出格式 3

5