Fibonacci Number

题意翻译

# 题目描述 斐波那契数列对10^13取模的定义如下： 　　1、F0 = 0, F1 = 1 　　2、Fi = (Fi-1 + Fi-2) mod (10^13) （i >= 2） 　 输入一个数x，问x是否在斐波那契数列当中出现过，如果出现过，最早出现在哪个位置。 # 输入格式 一行，一个整数x。 # 输出格式 一行，表示x在数列中最早出现的位置，如果没有出现过，则输出-1。

题目描述

John Doe has a list of all Fibonacci numbers modulo $ 10^{13} $ . This list is infinite, it starts with numbers $ 0 $ and $ 1 $ . Each number in the list, apart from the first two, is a sum of previous two modulo $ 10^{13} $ . That is, John's list is made from the Fibonacci numbers' list by replacing each number there by the remainder when divided by $ 10^{13} $ . John got interested in number $ f $ ( $ 0<=f&lt;10^{13} $ ) and now wants to find its first occurrence in the list given above. Help John and find the number of the first occurence of number $ f $ in the list or otherwise state that number $ f $ does not occur in the list. The numeration in John's list starts from zero. There, the $ 0 $ -th position is the number $ 0 $ , the $ 1 $ -st position is the number $ 1 $ , the $ 2 $ -nd position is the number $ 1 $ , the $ 3 $ -rd position is the number $ 2 $ , the $ 4 $ -th position is the number $ 3 $ and so on. Thus, the beginning of the list looks like this: $ 0,1,1,2,3,5,8,13,21,... $

输入输出格式

输入格式

The first line contains the single integer $ f $ ( $ 0<=f&lt;10^{13} $ ) — the number, which position in the list we should find. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出格式

Print a single number — the number of the first occurrence of the given number in John's list. If this number doesn't occur in John's list, print -1.

输入输出样例

输入样例 #1

13

输出样例 #1

7

输入样例 #2

377

输出样例 #2

14