Negative Base

It is known that the binary positional numeral system works as follows: denoting a nonnegative integer $x$ as a string "$x\_k \ldots x\_2 x\_1 x\_0$" of zeroes and ones means that $x = x\_k \cdot 2^k + \ldots + x\_2 \cdot 2^2 + x\_1 \cdot 2^1 + x\_0 \cdot 2^0$. The leading zeroes are omitted, so $x\_k = 1$, except the case when $x = 0$ which is denoted as "$0$".

The negabinary notation works in a similar way: denoting an number $x$ as a string "$x\_k \ldots x\_2 x\_1 x\_0$" of zeroes and ones means that $x = x\_k \cdot (-2)^k + \ldots + x\_2 \cdot (-2)^2 + x\_1 \cdot (-2)^1 + x\_0 \cdot (-2)^0$. The leading zeroes are also omitted, so $x\_k = 1$, except the case when $x = 0$ which is denoted as "$0$". It turns out that this notation has a unique representation for every integer (as opposed to only nonnegative integers).

Negabinary notation of numbers from $-7$ to $8$:

Given an integer $k$, find a number which has at least $k$ consecutive zeroes in its negabinary representation. Of all such numbers, find the one which has the least absolute value. If there are still several answers, pick the one with the shortest negabinary representation.

The first line of input contains an integer $k$ ($1 \le k \le 30$).

Print one integer: the answer to the problem.