数字转换

数字转换

Description

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

Format

Input

输入一个正整数n。

Output

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

Sample 1

Input

7

Output

3

【样例说明】
种方案为:4→3→1→7。

Limitation

1s, 128MiB for each test case.
【数据范围】
对于10%的数据,n = 4
对于30%的数据,n <= 100
对于100%的数据,n <= 50000

Source