Binary Palindromes

Problem Description

For a positive integer $n$, convert it to its binary representation without leading zeros. If this binary sequence reads the same from left to right as from right to left, the number is called a binary palindrome. For example, $9$ in binary is $(1001)_2$, a binary palindrome; $12$ in binary is $(1100)_2$, not a binary palindrome.

Your task: given a positive integer $n$, count how many binary palindromes lie in the range from $1$ to $n$.

Input Format

One line containing a positive integer $n$.

Output Format

One line containing one number: the count of binary palindromes in the range $1$ to $n$.

Sample Input

15

Sample Output

6

Sample Explanation

For input $15$, we list all binary palindromes from $1$ to $15$:

• $1$ in binary is $1$, a palindrome;
• $2$ in binary is $10$, not a palindrome;
• $3$ in binary is $11$, a palindrome;
• $4$ in binary is $100$, not a palindrome;
• $5$ in binary is $101$, a palindrome;
• $6$ in binary is $110$, not a palindrome;
• $7$ in binary is $111$, a palindrome;
• $8$ in binary is $1000$, not a palindrome;
• $9$ in binary is $1001$, a palindrome;
• $10$ in binary is $1010$, not a palindrome;
• $11$ in binary is $1011$, not a palindrome;
• $12$ in binary is $1100$, not a palindrome;
• $13$ in binary is $1101$, not a palindrome;
• $14$ in binary is $1110$, not a palindrome;
• $15$ in binary is $1111$, a palindrome.

Thus there are $6$ binary palindromes, so output $6$.

Constraints

$1 \le n \le 10^5$