Minimum Fibonacci Sum

You are given a positive integer \(N\) satisfying \(1 \leq N \leq 10^9\). Your task is to determine the minimum number of Fibonacci numbers whose sum is equal to \(N\). The Fibonacci sequence is defined as \(F_1 = 1\), \(F_2 = 1\) and for \(n \ge 3\), \(F_n = F_{n-1} + F_{n-2}\). According to Zeckendorf's theorem, every positive integer can be represented uniquely as a sum of non-consecutive Fibonacci numbers. Note that if \(N\) is itself a Fibonacci number, the answer is 1.

inputFormat

The input consists of a single line containing one integer \(N\).

outputFormat

Output a single integer representing the minimum number of Fibonacci numbers whose sum equals \(N\).

8

1