Problem Description

There is a rectangle with 2 rows and \( n \) columns, with some of its cells already occupied. You need to cover all unoccupied cells using \( 1 \times 2 \) or \( 2 \times 1 \) tiles, ensuring that no cell is covered twice. Let the number of possible arrangements be \( m \).

Given \( m \), find the smallest \( n \) such that there exists a configuration of occupied cells allowing exactly \( m \) ways to cover the unoccupied cells. If no such \( n \) exists, output NIE.

Input Format

A single line containing a positive integer \( m \).

Output Format

If a solution exists, output the value of \( n \).

If no solution exists, output NIE.

Sample Input and Output

Input Sample #1

4

Output Sample #1

5

Input Sample #2

101

Output Sample #2

NIE

Input Sample #3

9

Output Sample #3

7

Input Sample #4

11

Output Sample #4

NIE

Input Sample #5

500

Output Sample #5

20

Input Sample #6

112233445566778899

Output Sample #6

NIE

Notes/Hints

For all data, \( 1 \leq m \leq 10^{18} \).

见题面 Input 部分

见题面 Output 部分