P9238 [Lanqiao Cup 2023 NOI Qualifier A] Flipping Coins

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.

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

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

#### 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