Background

Translated from XXIX Olimpiada Informatyczna – Stage I Domino。

Problem Description

There is a $2$-row, $n$-column rectangle, where some cells are blocked. You need to use $1\times 2$ or $2\times 1$ dominoes to cover all unblocked cells, and no cell may be covered twice. Let the number of ways be $m$.

Given $m$, find the smallest $n$ such that there exists a way to choose the blocked cells so that the number of tilings is exactly $m$. If there is no solution, output NIE.

Input Format

One line with a positive integer $m$。

Output Format

If there is a solution, output your answer $n$。

If there is no solution, output NIE。

4

5

101

NIE

9

7

11

NIE

500

20

112233445566778899

NIE

Hint

For all testdata, $1\leq m\leq 10^{18}$。

Constraints

Translated by ChatGPT 5