Problem Description

Xiao Lan is drawing triangles. He first fixes the length of one side of the triangle as $x$. You need to find how many positive integers $y$ satisfy all of the following conditions:

• $1 \le y \le x$;
• The three numbers $x$, $y$, and $x | y$ can form the side lengths of a non-degenerate triangle.

Here, $x | y$ denotes the bitwise OR result of $x$ and $y$ in binary.

Note: A triangle is non-degenerate, which means its three side lengths $a, b, c$ must all be positive and satisfy the triangle inequalities: $a + b > c$, $a + c > b$, and $b + c > a$.

If any inequality becomes an equality (for example, $a + b = c$), then the triangle is degenerate (the three points are collinear).

Input Format

Input one line containing a positive integer $x$.

Output Format

Output one line containing an integer representing the answer.

10

7

Hint

Sample Explanation

Valid values of $y$ are: $2, 3, 6, 7, 8, 9, 10$.

Constraints

For $30\%$ of the testdata, $1 \le x \le 10^3$.

For all testdata, $1 \le x \le 10^{16}$.

Translated by ChatGPT 5