1159. Rin 和快速迭代

Rin 最近喜欢上了数论。

然而数论实在太复杂了,她只能研究一些简单的问题。

这天,她在研究正整数因子个数的时候,想到了一个快速迭代算法。设 f(x)x 的因子个数,将 f 迭代下去,Rin 猜想任意正整数最终都会变成 2。 例如 f(12)=6,f(6)=4,f(4)=3,f(3)=2

她希望你帮她验证一下。她会给你一个正整数 n,让你输出它在迭代过程中,第一次迭代成 2 的迭代次数。

输入

一个正整数 n \ (1 \leq n \leq 10^{12})

输出

一个正整数,为 n 迭代至 2 的次数。

样例

标准输入 复制文本
12
标准输出 复制文本
4

提示

  • 12 的因子共 6 个:1,2,3,4,6,12
  • 6 的因子共 4 个:1,2,3,6
  • 4 的因子共 3 个:1,2,4
  • 3 的因子共 2 个:1,3

来源

2020 牛客寒假算法基础集训营

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 114
通过 50