For a negative base 3 integer represented as $(a_ma_{m-1}\cdots a_0)_{-3}$, where each digit $a_i\in\set{0, 1, 2}$, the actual value of the number is calculated as $\sum_{i=0}^m a_i(-3)^i$. It can be demonstrated that every integer has a unique representation in this negative base system.

Input: A decimal integer $n$.

Output: Its representation in negative base 3 without leading zeros.

Constraints: $-44286\le n\le 14762$.

Example Input

-1

Example Output

12