说明

本题不再额外提供样例文件。

题目描述

对于一个整数 a，记它的真因子之和为 b。若 b < a，则 a 和 b 可以互相变换。

例如，当 a = 4 时，4 的真因子有 1, 2，所以 b = 1 + 2 = 3，则 4 和 3 可以互相变换。

再如，当 a = 5 时，5 的真因子只有 1，所以 b = 1，则 5 和 1 可以互相变换。

给你一个整数 m，你可以从不超过 m 的正整数中任选一个开始进行变换，要求每次变换不能得到一个已经变换出现过的整数（包括初始选择的数），且不允许变换成超过 m 的整数。

问：选择哪一个整数，可以使得你变换的次数最多？你只需要输出最多可以变换的次数。

输入格式

一行，一个整数 m。

输出格式

一个整数，表示答案。

样例1输入

5

样例1输出

3

样例1解释

变换方案不唯一，以下是一种可能方案：

5 → 1 → 3 → 4。

样例2输入

12345

样例2输出

29

数据范围

100% 的数据：1 ≤ m ≤ 50000。