You might be familiar with the binomial coefficient ${m \choose k}$ defined as ${m \choose k} = \frac{m!}{k!(m-k)!}$, where $m$ and $k$ are non-negative integers and $k \leq m$. Let $T_2(n)$ be the number of odd binomial coefficients such that $0 \le k \le m < n$. The most useful mathematical inequality you will learn during this competition is\[ 0.812556 n^{\log _2 3} \le T_2(n) \le n^{\log _2 3}. \]

Emma doesn’t like such imprecise inequalities and would like to calculate $T_2(n)$ exactly. Can you help her?

-----Input-----
The input contains one line with one integer $n, 1 \leq n \le 10^{11}$.

-----Output-----
Output one line with the value of $T_2(n)$.

-----Examples-----
Sample Input:
4
Sample Output:
9

见题面

见题面