0939 - 兎(三番煎じ)

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer ei1620 / x 12 / 統計 /


TLE
1sec
MLE
64MB
得点
1

問題

ある日、いづなはこんなことを聞いてきた。

・1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。
・兎が死ぬことはない
・この条件のもとで、産まれたばかりの1つがいの兎は何ヶ月の間に n つがいの兎になるか?

いづなの質問に答えるために、あなたは何とかして答え求めることにした。


「前とは逆、です!」

入力

n

最終的なつがいの数を表す整数 n が入力される。

出力

上記の条件の下、答えを求め出力せよ。なお、答えが複数ある場合は空白区切り昇順で出力せよ。出力の最後に改行を入れることを忘れずに。

制約

全ての入出力ケースについて以下を満たす。

  • 1 ≦ n ≦ 4660046610375530309
  • n の値はフィボナッチ数である。

入出力例

入力例1

2

出力例1

2

入力例2

13

出力例2

6