题目描述

对于一个正整数 $n$，我们将其转换为不含前导零的二进制表示，如果这个二进制序列从左向右读与从右向左读完全相同，则称该数为二进制回文数。

例如，$9$ 的二进制表示为 $(1001)_2$，是二进制回文数；而 $12$ 的二进制表示为 $(1100)_2$，则不是二进制回文数。

你的任务是：给定一个正整数 $n$，计算在 $1$ 到 $n$ 的范围内（包含 $1$ 和 $n$），二进制回文数的数量。

输入格式

输入仅包含一行，一个正整数 $n$。

输出格式

输出一行，包含一个整数，表示在 $1$ 到 $n$ 的范围内二进制回文数的数量。

样例输入 1

15

样例输出 1

6

说明

样例解释

在 $1$ 到 $15$ 的范围内，二进制回文数共有 $6$ 个，分别是：

• $1 = (1)_2$
• $3 = (11)_2$
• $5 = (101)_2$
• $7 = (111)_2$
• $9 = (1001)_2$
• $15 = (1111)_2$

数据范围

• 对于所有测试点，保证 $1 \le n \le 10^5$。
• 保证所有的输入数值均为整数。