题目描述

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

输入格式

输入一个正整数$\red{ n}$。

输出格式

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

样例

输入样例

7

输出样例

3

一种方案为 $\red{4\to 3\to 1\to 7}$。

提示

对于 $\red{100\%}$ 的数据，$\red{1\le n \le 50000}$。