有一个函数的定义如下

$\displaystyle f(x)= \begin{cases} 0 && x \le 0 \\ 1 && x=1 \\ 3f(\frac{x}{2})-1 && x > 1\ \ and\ \ \ x\%2=0 \\ 3f(\frac{x+1}{2})-1 && x > 1\ \ and\ \ \ x\%2=1 \end{cases}$

其中 $x$ 为整数。

输入格式

输入一个整数 $x(-10^5 \le x \le 10^5)$*。

输出格式

输出函数 $f(x)$ 值。

输出时每行末尾的多余空格，不影响答案正确性

样例输入1

3

样例输出1

5

样例输入2

10

样例输出2

41