3234 - 数字转换

如果一个数x的所有约数的和值为y(不包括它本身),y比它本身x小,那么x可以变成y,y也可以变成x。例如,4可以变成3,1可以变为7。限定所有的数字变换在不超过n的正整数范围内进行,求不断进行数字变换且没有重复数字出现的最多变换步数。

输入

输入一个正整数n。

输出

输出不断进行数字变换且没有重复数字出现的最多变换步数。

样例

输入

7

输出

3

提示

【样例说明】

  一种方案为:4->3->1->7。

【数据规模】

n≤50000。

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题