Lucky Number

Time Limit: 1 sec

 

The Problem

A number is said to be lucky if it has all contagious number of 1’s in binary representation. For example 1, 3, 7, 15 are lucky numbers. Binary of 1 is 1, binary of 3 is 11, binary of 7 is 111, binary of 15 is 1111 and so on.

In this problem, you will be given an positive integer n. Your job is to count the total lucky numbers smaller than or equal to n.

 

The Input

There are several lines of input, and each line contains a positive integer n (0 < n <= 100000000). Input is terminated by EOF.

 

The Output

For each line of input you have to print total lucky numbers smaller than or equal to n in a seperate line.

 

Sample Input

5

22

125

 

Sample Output

2

4

6

 

 

 

Inter University Programming Contest - Summer 2019 [BGC Trust University Bangladesh]

Problem Setter: Shahin ShamS