도미노

Bajtek은 $2 \times n$ 크기의 직사각형을 $2 \times 1$ 도미노 조각으로 덮는 놀이를 한다. 너비가 $n$인 직사각형은 1 × 1 칸 $2n$개로 이루어지며, Bajtek은 그중 일부 칸을 칠할 수 있다. 칠하지 않은 칸은 도미노 조각이 서로 겹치지 않게 모두 덮을 수 있어야 한다. 조각은 회전해도 된다. 또 그렇게 덮는 방법이 정확히 $m$가지이기를 원한다. 마지막으로 이런 조건을 만족하는 가장 작은 직사각형을 찾고자 한다.

아래 그림은 너비가 $n = 6$인 직사각형에서 칸 두 개를 칠한 모습이다. 칠하지 않은 나머지 10칸은 정확히 4가지 방법으로 덮을 수 있다. 그림에는 그중 두 방법을 나타냈다. 도미노 조각은 잘 보이도록 조금 작게 그렸다.

이 배치는 $m = 4$에 대한 최적해가 아니다. $n = 5$인 배치가 존재하기 때문이다.

첫 번째이자 유일한 줄에 자연수 $m$이 주어진다 ($1 \le m \le 10^{18}$).

첫 번째이자 유일한 줄에, 칸을 칠해서 정확히 $m$가지 방법으로 덮을 수 있는 직사각형의 가장 작은 너비 $n$을 출력한다. 그런 직사각형이 없으면 NIE만 출력한다.