問題文
fi 佛纳奇数列是以下递推公式表示的数列 F_0,\ F_1,\ F_2,\ …\ (=0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ …) ,fi 佛纳奇数是出现在这个数列中的数 F_i\ (i \geq 0) 。
- F_{0} = 0
- F_{1} = 1
- F_{i+2} = F_{i} + F_{i+1} (i \geq 0)
某个正整数 n ,考虑将其表示为若干 fi 佛纳奇数的和。
此时,作为和为正整数 n 的 fi 佛纳奇数的个数所能取的最小值。
但是,同一个fi斐波那契数也可以使用多次,每次使用都单独计算。
入力
n
- 正整数 n (1 \leq n \leq 10^{10}) 是 1 行中给出。
部分点
出力
请注意,行尾需要换行。 定义
入力例 1
10
出力例 1
2
-
10 是最小的 5 ,\ 5 可以得到第 2 可以表示为由最少个fi斐波那契数的和。
入力例 2
11
出力例 2
2
-
11 是最小的 3 ,\ 8 可以得到第 2 可以表示为由最少个fi斐波那契数的和。
入力例 3
10000000000
出力例 3
16