Counting Fixed Points of the Kathy Function

Tiger loves mathematics and has been introduced to the Kathy function by his teacher. The Kathy function f is defined as follows:

$$\begin{cases} f(1)=1,\\ f(3)=3,\\ f(2n)=f(n),\\ f(4n+1)=2f(2n+1)-f(n),\\ f(4n+3)=3f(2n+1)-2f(n) \end{cases}$$

After some study, Tiger discovered that many positive integers satisfy f(n)=n. It turns out that f(n)=n if and only if n is an odd positive integer whose binary representation is a palindrome. For example, the binary representations of 1, 3, 5, 7, and 9 are "1", "11", "101", "111", and "1001", respectively – all palindromic.

Your task is: Given a positive integer m, count the number of positive integers n (with n ≤ m) such that f(n)=n.

inputFormat

The input consists of a single positive integer m (1 ≤ m ≤ 10^18).

outputFormat

Output a single integer — the count of positive integers n (with n ≤ m) satisfying f(n)=n.

sample

1

1