数字转换

题目描述

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

输入

输入一个正整数n。

输出

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

样例

提示

【样例说明】

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

【数据规模】

n≤50000。