Fibonacci Subset Sum

Given an integer n, return the minimum number of Fibonacci numbers required to sum up to n.

Constraints

• 1 ≤ n < 2 ** 31

https://binarysearch.com/problems/Fibonacci-Subset-Sum

Examples

Example 1

Input

• n = 9

Output

• answer = 2

Explanation

We can use the Fibonacci numbers [1, 8] to sum to 9.

Solution