#4294. [PA2015]Fibonacci

内存限制:64 MiB 时间限制:10 Sec

题目描述

众所周知,斐波那契数列F满足:
F[0]=0,F[1]=1,F[m]=F[m-1]+F[m-2](m>=2)
现在给出一个数字串S,请找到一个k使得F[k]以S为结尾。

输入格式

包含一行一个数字串S,S的长度不超过18。

输出格式

输出满足条件的数字k,且k需要满足0<=k<10^100。若有多组解,输出任意一组,若无解,输出NIE。

样例

样例输入


			
025

样例输出


			
1525

数据范围与提示

请不要提交,尚无SPJ