题目描述

一个正整数 $X$ 被称为“好数（good integer）”，当且仅当它满足以下条件：

存在一对正整数 $(a, b)$，使得：

例如，$400$ 是一个好数，因为：

现在给定一个正整数 $N$，请你计算在区间 $[1, N]$ 内（包含两端）有多少个好数。

输入格式

输入仅一行

第一行包括一个正整数$N$

• $1 \leq N \leq 10^{18}$

输出格式

输出区间 $[1, N]$ 内的好数个数。

样例输入

20

样例输出

5

说明

样例解释

在 $1$ 到 $20$ 之间，有以下五个好数：

• $2 = 2^1 \times 1^2$
• $4 = 2^2 \times 1^2$
• $8 = 2^3 \times 1^2$
• $16 = 2^4 \times 1^2$
• $18 = 2^1 \times 3^2$