Problem Description

Given $n$ coins placed in order. At the beginning, only the $1$st coin is facing down, and all other coins are facing up. In each operation, you may choose any integer $i$ and flip all coins at positions $j$ that satisfy $j \bmod i = 0$.

Find the minimum number of operations needed to make all coins face up.

Input Format

The input consists of one line containing an integer $n$.

Output Format

Output one line containing an integer, the minimum number of operations.

7

6

1131796

688042

Hint

Scale and assumptions for test cases.

For $30\%$ of the test cases, $n \leq 5 \times 10^6$.

For $70\%$ of the test cases, $n \leq 10^9$.

For all test cases, $1 \leq n \leq 10^{18}$.

Translated by ChatGPT 5