题目描述

题目译自 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。

025

1525

222

NIE