Description

As everyone knows, the Fibonacci sequence $F$ satisfies:

Now you are given a digit string $S$. Please find the smallest $k$ such that $F_k$ ends with $S$.

Input Format

One line containing a digit string $S$.

Output Format

Output the smallest integer $k$ that satisfies the condition.

If there is no solution, output NIE.

025

1525

Hint

Constraints: for $100\%$ of the testdata, the length of $S$ is at most $18$, and $0\le k<10^{100}$.

Translated by ChatGPT 5