问题描述

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

• 存在一对正整数$(a, b)$ ，使得 $X = 2^a \times b^2$。

例如，$400$ 是一个好整数，因为 $400 = 2^2 \times 10^2$。

给定一个正整数 $N$，找出在 $1$到$N$（包括 $1$ 和 $N$）之间的好整数的数量。

输入

一个正整数$N$

输出

输出在 $1$ 到$N$（包括 $1$ 和$N$）之间的好整数的数量。

样例输入 1

20

样例输出 1

5

在 1 到 20 之间有五个好整数：2，4，8，16 和 18。 因此，输出 5。

样例输入 2

400

样例输出 2

24

样例输入 3

1234567890

样例输出 3

42413

数据范围

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

• 注意，输入可能无法用 32 位整数类型存储。