The Fibonacci numbers are defined as follows: $F_0 = 0, F_1 = 1, F_m = F_{m-1} + F_{m-2}$ for $m \ge 2$.

Your task is to find an integer $k$ such that the decimal representation of $F_k$ (without leading zeros) ends with a given sequence of digits.

Input

The only line of input contains a string consisting of $n$ digits $c_1c_2 \dots c_n$ ($1 \le n \le 18, 0 \le c_i \le 9$).

Output

If there exists at least one integer $k$ such that $0 \le k < 10^{100}$ and the decimal representation of $F_k$ ends with the sequence of digits $c_1c_2 \dots c_n$, output any such number. Otherwise, output the word NIE.

Examples

Input 1

025

Output 1

1525

Input 2

222

Output 2

NIE