Domino

Time limit10sMemory limit1024 MB

Summary

Find the smallest width n of a 2 x n board where painting some cells leaves exactly m domino tilings of the rest, or report NIE.

Level: Medium7 of 10
Topics: Math, Dynamic programming, Number theory
Solved: No attempts yet

Problem

Bajtek plays a game of covering $2 \times n$ rectangles with $2 \times 1$ domino tiles. A rectangle of width $n$ consists of $2n$ unit cells, and Bajtek may paint over some of them. He wants every unpainted cell to be coverable by dominoes without overlap. Tiles may be rotated. He also wants this to be possible in exactly $m$ ways. Last, he wants the smallest rectangle that can be covered this way. Can you help him?

The figure below shows a rectangle of width $n = 6$ with two cells painted over. The other 10 cells can be covered by dominoes in exactly 4 ways. The figure shows two of these ways. The tiles are drawn slightly smaller for clarity.

This arrangement is not optimal for $m = 4$ , because an arrangement with $n = 5$ exists.

Input

The first and only line contains one natural number $m$ ( $1 \le m \le 10^{18}$ ).

Output

The first and only line must contain one natural number $n$ , the smallest possible width of a rectangle that can be painted and covered in exactly $m$ ways. If no such rectangle exists, print only the word NIE instead.

Examples2

Example 1
Input
```
4
```
Expected output
```
5
```
Example 2
Input
```
101
```
Expected output
```
NIE
```