题目描述

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

输入格式

输入一个正整数 \(n\)。

输出格式

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

样例数据

样例输入

7

样例输出

3

样例说明

一种方案为 \(4\to 3\to 1\to 7\)。

限制与提示

对于 \(100\%\) 的数据，\(1\le n \le 50000\)。