Background

Problem Description

There is a rooted tree with $n$ nodes, and the root is $1$.

For $i > 1$, let $m_i$ be the smallest prime factor of $i$. Then the parent of node $i$ is $\frac{i}{m_i}$.

Find the size of the maximum independent set of this tree.

Input Format

One line with a non-negative integer $n$, representing the number of nodes in the tree.

Output Format

One line with a non-negative integer, representing the size of the maximum independent set of this tree.

7

4

114514

68372

10000000000

5971085299

Hint

Constraints

• For $10\%$ of the testdata, $1 \leq n \leq 10^7$.
• For $30\%$ of the testdata, $1 \leq n \leq 10^8$.
• For $50\%$ of the testdata, $1 \leq n \leq 10^{9}$.
• For $70\%$ of the testdata, $1 \leq n \leq 10^{10}$.
• For $100\%$ of the testdata, $1 \leq n \leq 10^{11}$.

Translated by ChatGPT 5