피보나치 수의 마지막 13자리

$F_n$을 $n$번째 피보나치 수라 하고, $G_n = F_n \bmod 10^{13}$이라고 하자. 즉 $G_n$은 $F_n$의 마지막 13자리다.

$n$이 주어졌을 때, $G_i = n$인 가장 작은 $i$를 찾는 프로그램을 작성하시오.

피보나치 수의 앞부분은 다음과 같다.

• $F_0 = 0$
• $F_1 = 1$
• $F_2 = 1$
• $F_3 = 2$
• $F_4 = 3$
• $F_5 = 5$
• $F_6 = 8$
• $F_7 = 13$
• $F_8 = 21$

첫째 줄에 정수 $n$($1 \le n \le 10^{13}$)이 주어진다.

$G_i = n$인 가장 작은 $i$를 출력한다. 그러한 $i$가 없으면 -1을 출력한다. 답은 $10^{13}$보다 클 수 있다.