5. Beware, Evil Numbers!
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In mathematics, a non-negative integer with an even number of ones in its binary notation is called an evil number (for example, number 5 is evil, as it has two ones in its binary notation). These numbers are used in number theory when studying the Morse–Thue sequence and are applied in fractal image compression algorithms.

A positive integer is called very evil if it is even and the number of ones in its binary notation is also even. These are such numbers as 6, 10, 12, 18, 20, etc.

Given $$$n$$$, find the number of very evil numbers which do not exceed $$$n$$$.

Input

The only line of the input file contains an integer number $$$n$$$ ($$$1 \le n \le 10^{9}$$$).

Output

Output a single integer, which is the number of very evil numbers not exceeding $$$n$$$.

Scoring

Solutions that run correctly when $$$n$$$ does not exceed $$$10^{5}$$$ score 30 points.

Solutions that run correctly when $$$n$$$ is an exact power of 2 score 30 points.

Example
Input
20
Output
5