13729번 - 1013 피보나치

F_n을 n번째 피보나치 수, G_n을 F_n % 10¹³이라고 하다.

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

피보나치 수의 첫 부분은 아래와 같다.

• F₀ = 0
• F₁ = 1
• F₂ = 1
• F₃ = 2
• F₄ = 3
• F₅ = 5
• F₆ = 8
• F₇ = 13
• F₈ = 21

첫째 줄에 정수 n(1 ≤ n ≤ 10¹³)이 주어진다.

G_i = n인 가장 작은 i값을 출력한다. 만약 그러한 i가 없으면 -1을 출력한다.