Problem Description

Tiger likes math very much, so he joined the school's extracurricular math club. In the club, the teacher introduced the Kathy function to Tiger, which is defined as:

$$\left\{ \begin{aligned} &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{aligned} \right.$$

Tiger became very interested in the Kathy function, and through studying he found that many numbers $n$ satisfy $f(n)=n$.

Given a number $m$, he wants you to find the number of positive integers $n$ such that $f(n)=n$, where $n \leq m$.

Input Format

The input contains a single line with an integer $m$.

Output Format

Output a single integer: the number of positive integers $n$ with $n \leq m$ that satisfy $f(n)=n$.

5

3

Hint

Constraints

For all testdata, it is guaranteed that $1 \leq m \leq 10^{100}$.

Translated by ChatGPT 5