Bajtek is playing with covering $2 \times n$ rectangles with $2 \times 1$ dominoes. A rectangle of width $n$ consists of $2n$ fields (of size $1 \times 1$), some of which Bajtek can paint.

Bajtek wants it to be possible to cover all unpainted fields without overlapping dominoes (dominoes can be rotated). Moreover, Bajtek would like this to be possible in exactly $m$ ways. Finally, he would like to find the smallest rectangle that can be covered in this way. That is a lot of requirements, will you help him?

The figure below shows a rectangle of width $n = 6$, in which two fields have been painted. The remaining 10 fields can be covered with dominoes in exactly 4 ways. Two of these ways are shown in the figure (the dominoes have been slightly reduced in size only for better visualization of the situation):

However, this is not the optimal solution for $m = 4$, because there exists a solution where $n = 5$.

Write a program that, for a given $m$, determines the smallest width of a rectangle $n$ in which it is possible to paint the fields such that the remaining fields can be covered with $2 \times 1$ dominoes in exactly $m$ ways.

Input

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

Output

The first and only line of output should contain a natural number $n$ representing the smallest possible width of the sought rectangle. If no such rectangle exists, print only the word NIE instead.

Evaluation tests

• Test 1: $m = 9$, result is $n = 7$;
• Test 2: $m = 11$, result is NIE;
• Test 3: $m = 500$, result is $n = 20$;
• Test 4: $m = 112233445566778899$, result is NIE.

Examples

Input 1

4

Output 1

5

Input 2

101

Output 2

NIE

Subtasks

The test set is divided into the following subtasks. Each subtask consists of one or more separate test groups.