题目背景

$$f(x) = \left\{\begin{array}{l} 0 & x\le 0 \\ 1& x=1\\3f(\frac{x}{2} )-1& x>1 \space and\space x\mod 2=0\\ 3f(\frac{x+1}{2} )-1&x>1 \space and\space x\mod 2=1\\ \end{array}\right. $$

题目描述

根据“题目背景”的递归公式来求出 $f(x)$

输入

输入 $x$

输出

输出 $f(x)$

样例

2

2

提示

$0<=x<=1e6$