Minimal Columns for Exact Domino Tiling Count

You are given a 2×n rectangle. Some of the cells in the rectangle may be occupied (blocked). In each column the cells must be treated collectively – that is, a column is either completely free or completely blocked. For any configuration (assignment of free/blocked columns), the free columns will form one or more contiguous segments. Each contiguous segment of free columns (of length L) can be tiled in exactly \(F_{L+1}\) ways using dominoes of size 1×2 (horizontal) or 2×1 (vertical), where \(F_k\) denotes the k-th Fibonacci number defined by \(F_1=1,\,F_2=1,\,F_{k}=F_{k-1}+F_{k-2}\) for \(k\ge3\>.

The overall number of tilings is the product of tilings for each free segment. You are given an integer \(m\). Determine the minimum number of columns \(n\) for which there exists some way to choose occupied columns (and hence free segments) so that the total number of tilings is exactly \(m\). If no such \(n\) exists, output NIE.

Note: In a column, either both cells are free or both cells are occupied. When free columns form several separated segments, at least one blocked column is needed between two free segments. For a segment of free columns of length \(L\), the tiling count is \(F_{L+1}\). If there are several free segments of lengths \(L_1, L_2, \dots, L_r\) (with \(r\ge 1\)), then the board has at least \(L_1+L_2+\cdots+L_r+(r-1)\) columns in total.

For example, if the board is entirely free (i.e. one segment of length \(n\)), the number of tilings is \(F_{n+1}\). On the other hand, a board with free segments of lengths 2 and 3 (with one blocked column in between) has \(n = 2+3+1 = 6\) columns, and the number of tilings is \(F_3 \times F_4 = 2 \times 3 = 6\>.

inputFormat

The input consists of a single integer \(m\) (1 ≤ m ≤ 10¹⁸).

outputFormat

Output the minimum number of columns \(n\) for which there exists some configuration of occupied columns such that the number of domino tilings is exactly \(m\). If no such configuration exists, output NIE.

sample

1

1