F - Fibonaccyan Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

penguinman はフィボナッちゃんに恋をしました。

フィボナッちゃんがある正整数 P を好きなことを知った penguinman は、F_i が P で割り切れる最小の正整数 i を見つけ、プレゼントすることにしました。 ここで、F は以下のような漸化式で表される数列です。

  • F_1=F_2=1
  • F_{i+2}=F_{i+1}+F_i\ (1\leq i)

penguinman のためにそのような整数 i を見つけるか、そのような i が存在しないことを教えてあげてください。

制約

  • 入力は全て整数である。
  • 1\leq P\leq3000

入力

入力は以下の形式で標準入力から与えられます。

P

出力

問題文中の条件を満たす整数 i が存在しない場合、-1 を出力してください。

存在する場合、i を出力してください。

出力の最後に改行を忘れないでください。

入力例1

3

出力例1

4

F_1=1,\ F_2=1,\ F_3=2,\ F_4=3 より、F_i が 3 で割り切れる最小の i は 4 です。

入力例2

10

出力例2

15

入力例3

3000

出力例3

1500