Yêu cầu: Cho dãy số Fibonacci có công thức: F1 = F2 = 1, Fn = F(n-1) + F(n-2) với mọi số nguyên n lớn hơn 2. Người ta chứng minh được rằng, với mọi số nguyên dương X đều phân tích được dưới dạng tổng của các số Fibonacci khác nhau. Ví dụ: 7 = 2 + 5, 10 = 2 + 8 = 2 + 3 + 5. Cho một số nguyên dương X, hãy tính xem cần ít nhất bao nhiêu số Fibonacci khác nhau để tổng của chúng bằng X.

Dữ liệu:

          - Một dòng duy nhất ghi số nguyên dương X(X<=10⁹)

Kết quả: In ra số lượng ít nhất các số Fibonacci có tổng bằng X