← 返回题目列表

AtCoder · abc400_c

F. 二的幂乘以平方

中文机器翻译题面 查看原题

分数: 350 点

问题陈述

正整数 当且仅当满足以下条件时, X 被称为好整数:

  • 存在一对正整数 (a,b) 这样 X = 2^a \times b^2.

例如, 400 是一个很好的整数,因为 400 = 2^2 \times 10^2.

给定一个正整数 N,找到之间的好整数的数量 1 和 N,包括在内。

约束

  • 1 \leq N \leq 10^{18}
  • N 是一个整数。

输入

输入由标准输入按以下格式给出:

N

输出

打印之间的好整数的数量 1 和 N,包括在内。


示例输入 1

20

示例输出 1

5

之间有五个好整数 1 和 20: 2, 4, 8, 16,和 18.
因此,打印 5.


示例输入 2

400

示例输出 2

24

示例输入 3

1234567890

示例输出 3

42413

请注意,输入可能不适合 32- 位整数类型。