题目背景

题目描述

有一棵 $n$ 个点的有根树，根是 $1$。

对于 $i>1$，记 $m_i$ 为 $i$ 的最小质因子，那么 $i$ 的父亲结点就是 $\frac{i}{m_i}$。

求这棵树的最大独立集的大小。

输入格式

一行一个非负整数 $n$ 代表树的点数。

输出格式

一行一个非负整数代表这棵树的最大独立集大小。

7

4

114514

68372

10000000000

5971085299

提示

• 对于 $10\%$ 的数据，$1\leq n\leq 10^7$。
• 对于 $30\%$ 的数据，$1\leq n\leq 10^8$。
• 对于 $50\%$ 的数据，$1\leq n\leq 10^{9}$。
• 对于 $70\%$ 的数据，$1\leq n\leq 10^{10}$。
• 对于 $100\%$ 的数据，$1\leq n\leq 10^{11}$。