[AdditionalFile5284.zip](file://AdditionalFile5284.zip?type=additional_file)

#5284. 「PA 2015」Fibonacci

标签: 传统 | 时间限制: 10000 ms | 内存限制: 64 MiB |

题目描述

题目译自 PA 2015 Runda 2 Fibonacci

斐波那契数的定义如下：

$$F_{0}=0, \quad F_{1}=1, \quad F_{m}=F_{m-1}+F_{m-2} \quad \text{对于} \ m \geq 2。$$

你的任务是找到一个 $k$，使得斐波那契数 $F_{k}$ 的十进制表示（不含前导零）以给定的数字序列结尾。

输入格式

输入的唯一一行包含一个由 $n$ 个数字组成的字符串 $\overline{c_{1} c_{2} \ldots c_{n}}$ $(1 \leq n \leq 18, 0 \leq c_{i} \leq 9)$。

输出格式

如果存在至少一个整数 $k$，满足 $0 \leq k < 10^{100}$ 且斐波那契数 $F_{k}$ 的十进制表示以数字序列 $\overline{c_{1} c_{2} \ldots c_{n}}$ 结尾，则输出任意一个这样的 $k$。否则，输出 NIE。

样例 1

输入

025

输出

1525

样例 2

输入

222

输出

NIE