### 问题描述 众所周知，斐波那契数列为 $1,1,2,3,5,8,\dots$，给定一个整数 $n$，请问 $n$ 最少可以分解为多少个斐波那契数的和。 ### 输入格式 输入共一行，包含一个整数 $n$，表示给定的整数。 ### 输出格式 输出共一行，包含一个整数，表示 $n$ 最少可以分解为多少个斐波那契数的和。 ### 样例输入 ``` 4 ``` ### 样例输出 ``` 2 ``` ### 评测数据规模 对于所有评测数据，$1 \leq n \leq 10^9$。