Fibonacci Representation

The Fibonacci sequence is defined as follows:

$$Fib_{0}=0,\,Fib_{1}=1,\,Fib_{n}=Fib_{n-2}+Fib_{n-1}\quad\text{for }n>1$$

Its first few elements are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Byteasar is investigating representations of numbers as sums or differences of Fibonacci numbers. For a given positive integer \(k\), he wonders what is the minimum representation, i.e. the minimum number of (not necessarily distinct) Fibonacci numbers required so that by adding or subtracting them appropriately one obtains \(k\). For example, the numbers can be represented as follows:

• $$10=5+5$$
• $$19=21-2$$
• $$17=13+5-1$$
• $$1070=987+89-5-1$$

Your task is to help Byteasar by writing a program that, for a given positive integer \(k\), determines the minimum number of Fibonacci numbers required to represent \(k\) as a sum or difference of Fibonacci numbers.

inputFormat

The input consists of a single positive integer \(k\).

For example:

10

outputFormat

Output a single integer that represents the minimum number of Fibonacci numbers required to represent \(k\) using addition and subtraction.

For example, the output for the input above is:

2

sample

10

2