Last 13 digits of a Fibonacci number

Let $F_n$ be the $n$-th Fibonacci number and let $G_n = F_n \bmod 10^{13}$. That is, $G_n$ is the last 13 digits of $F_n$.

Given $n$, write a program that finds the smallest $i$ with $G_i = n$.

The Fibonacci numbers start like this.

• $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$

The first line contains an integer $n$ ($1 \le n \le 10^{13}$).

Print the smallest $i$ with $G_i = n$. If no such $i$ exists, print -1. The answer can be greater than $10^{13}$.