A8651 | Fibonacci Number

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<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<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.