题目描述

给定一个模$10^{13}$意义下的非负整数$a$，求$a$第一次出现在模$10^{13}$意义下的斐波那契数列$F$中的第几项。 这里模意义下的斐波那契数列$F$定义如下：

$$\begin{cases}F_0≡0\\F_1≡1&(\bmod 10^{13})\\F_n=F_{n-1}+F_{n-2}(n≥2) \end{cases}$$

输入

一行一个非负整数$a$。

输出

一行一个整数$ans$，表示$a$第一次在数列$F$中出现的位置。 如果$a$不出现在数列$F$中，输出$-1$。

输入样例

1

输出样例

1

提示

【数据规模与约定】 对于10%的数据，保证$a$不会出现在数列$F$中。 对于另外30%的数据，保证答案不超过$10^7$。 对于100%的数据，保证0≤a<10^{13}。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。