시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 47 5 3 11.111%

문제

Fn을 n번째 피보나치 수, Gn을 Fn % 1013이라고 하다.

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

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

  • F0 = 0
  • F1 = 1
  • F2 = 1
  • F3 = 2
  • F4 = 3
  • F5 = 5
  • F6 = 8
  • F7 = 13
  • F8 = 21

입력

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

출력

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

예제 입력 1

13

예제 출력 1

7

예제 입력 2

377

예제 출력 2

14

예제 입력 3

10

예제 출력 3

-1

힌트

출처