题目描述

如果一个数𝑥 的约数之和 𝑦（不包括他本身）比他本身小，那么 𝑥 可以变成 𝑦，𝑦 也可以变成 𝑥。

例如，4 可以变为 3，1 可以变为7。

限定所有数字变换在不超过 𝑛 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。

输入格式

输入一个正整数𝑛。 1≤n≤50000

输出格式

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

输入数据1

7

输出数据1

3

样例解释

一种方案为：4→3→1→7。