题目描述

如果一个整数的二进制形式为若干个1后面跟着若干个0，则称这个数为 “趣味⼆进制”。例如 ，⼗进制数 12 的⼆进制表⽰为 1100， 16 的⼆进制表⽰为 10000，它们都是 趣味⼆进制数 。但 7 的⼆进制表⽰只含连续 1 但不含 0 就不属于 “趣味⼆进制” 数。在⼗进制数 1,2,…,n 之间 ，有多少个这样的趣味⼆进制数呢？

输入格式

一行一个整数，为n；

输出格式

一行一个整数，为1到n共有的有趣数字的数量。

样例数据

input

12

output

5

样例说明： 2（10），4（100），6（110），8（1000），12（1100），共五个。

数据范围与提示

对于 60% 的数据 ，有 n≤100,000。
对于100% 的数据 ，有 1≤n≤1,000,000,000。