Description

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

Input Format

输入一个正整数n。

Output Format

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

Sample

样例输入

7

样例输出

3

样例说明:

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

Hint

对于100%的数据，1<=n<=50000。