Description

If the sum of the divisors (excluding itself) of a number $x$, denoted as $y$, is less than $x$ itself, then $x$ can be transformed into $y$, and $y$ can also be transformed into $x$. For example, $4$ can be transformed into $3$, and $1$ can be transformed into $7$. All transformations are constrained to positive integers not exceeding $n$. Find the maximum number of transformation steps possible without repeating any numbers.

Input Format

Input a positive integer $n$.

Output Format

Output the maximum number of transformation steps possible without repeating any numbers.

Sample 1

One possible transformation sequence is $4\to 3\to 1\to 7$.

7

3

Data Range and Hint

For $100\%$ of the data, $1\le n \le 50000$.