P15434 [Lanqiao Cup 2025 National Python B] Triangle Construction

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 one line containing a positive integer $x$.

Output one line containing an integer representing the answer.

### 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