음수 기저

이진 위치 기수법은 다음과 같이 동작한다. 음이 아닌 정수 $x$를 0과 1로 이루어진 문자열 "$x\_k \ldots x\_2 x\_1 x\_0$"으로 나타내면 $x = x\_k \cdot 2^k + \ldots + x\_2 \cdot 2^2 + x\_1 \cdot 2^1 + x\_0 \cdot 2^0$이라는 뜻이다. 앞의 0은 생략하므로 $x\_k = 1$이고, $x = 0$인 경우만 "$0$"으로 나타낸다.

네가바이너리 표기법도 비슷하게 동작한다. 어떤 수 $x$를 0과 1로 이루어진 문자열 "$x\_k \ldots x\_2 x\_1 x\_0$"으로 나타내면 $x = x\_k \cdot (-2)^k + \ldots + x\_2 \cdot (-2)^2 + x\_1 \cdot (-2)^1 + x\_0 \cdot (-2)^0$이라는 뜻이다. 앞의 0은 역시 생략하므로 $x\_k = 1$이고, $x = 0$인 경우만 "$0$"으로 나타낸다. 이 표기법은 음이 아닌 정수뿐 아니라 모든 정수에 대해 유일한 표현을 가진다.

$-7$부터 $8$까지의 수를 네가바이너리로 나타내면 다음과 같다.

정수 $k$가 주어졌을 때, 네가바이너리 표현에 연속한 0이 적어도 $k$개 있는 수를 찾는다. 그러한 수 중에서 절댓값이 가장 작은 수를 찾는다. 그러한 수가 여러 개라면 네가바이너리 표현의 길이가 가장 짧은 수를 고른다.

첫째 줄에 정수 $k$가 주어진다. ($1 \le k \le 30$)

문제의 답이 되는 정수 하나를 출력한다.