#8795. 「一本通 5.2 例 3」数字转换

「一本通 5.2 例 3」数字转换

题目描述

如果一个数 xx 的约数(不包括他本身)的和 yy 比他本身小,那么 xx 可以变成 yyyy 也可以变成 xx。例如 44 可以变为 3311 可以变为 77。限定所有数字变换在不超过 nn 的正整数范围内进行,求不断进行数字变换且不出现重复数字的最多变换步数。

输入格式

输入一个正整数 nn

输出格式

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

样例

7
3

一种方案为 43174\to 3\to 1\to 7

数据范围与提示

对于 100%100\% 的数据,1n500001\le n \le 50000