Busy Beaver 得到了一个用十进制表示的正整数 $k$ ($1 \le k \le 10^{18}$)。接着，他重复执行以下操作：

选择 $k$ 中的一个大于 1 的数字。如果 $k$ 能被该数字整除，则将 $k$ 除以该数字。对得到的结果重复此过程，直到达到 1 或者无法再进行合法的操作。如果存在一种方式可以通过该操作将 $k$ 减小到 1，则称 $k$ 是合法的。

计算在 $1, \dots, N$ 的范围内有多少个合法的 $k$。

输入格式

输入的第一行包含给定的整数 $N$ ($1 \le N \le 10^{18}$)。

输出格式

输出一行，包含一个整数，表示从 1 到 $N$ 中可以通过该操作达到 1 的整数个数。

子任务

本题有两个子任务：

• (25 分)：$N \le 10^5$。
• (75 分)：无额外限制。

样例

样例输入 1

9

样例输出 1

9

样例输入 2

13

样例输出 2

10

说明

在第一个测试用例中，所有从 1 到 9 的整数都可以被其自身整除从而达到 1，因此答案为 9。

在第二个测试用例中，所有从 1 到 9 的整数都是合法的，如第一个测试用例所述。10、11 和 13 没有大于 1 的数字作为其自身的约数，因此无法减小到 1。然而，12 可以除以 2 得到 6，6 又可以除以 6 得到 1。因此，1 到 9 以及 12 是合法的，答案为 10。