题目描述

当数字能够被该数字二进制下 $1$ 的个数整除，则这个数字是优美的。例如：

• $6$ 是优美的，因为 $6$ 在二进制下有两个 $1$，$6$ 能够被 $2$ 整除。
• $5$ 不是优美的，因为 $5$ 在二进制下也有两个 $1$，但 $5$ 不能被 $2$ 整除。

给定 $n$，请问在 $1$ 到 $n$ 之间，有多少个优美的数字？

输入格式

单个整数表示 $n$

输出格式

单个整数表示结果

10

6

样例解释 1

1、2、4、6、8、10满足条件

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 10^5$
• 对于 $60\%$ 的数据，$1\leq n\leq 10^9$
• 对于 $100\%$ 的数据，$1\leq n\leq 10^{18}$