Rozkład Fibonacciego

Limit pamięci: 64 MB

Ciąg liczb Fibonacciego to ciąg liczb całkowitych zdefiniowany rekurencyjnie w następujący sposób:

Początkowe elementy tego ciągu to: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Bajtazar bada, jak różne liczby można przedstawić jako sumy lub różnice liczb Fibonacciego. Aktualnie zastanawia się, jak daną dodatnią liczbę całkowitą przedstawić jako sumę lub różnicę jak najmniejszej liczby (niekoniecznie różnych) liczb Fibonacciego. Na przykład, liczby 10, 19, 17 i 1070 można przedstawić minimalnie, odpowiednio, za pomocą 2, 2, 3 lub 4 liczb Fibonacciego:

Pomóż Bajtazarowi! Napisz program, który dla danej dodatniej liczby całkowitej wyznaczy minimalną liczbę liczb Fibonacciego potrzebnych do przedstawienia liczby jako ich sumy lub różnicy.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita () oznaczająca liczbę zapytań. W kolejnych wierszach będzie znajdowało się po jednej dodatniej liczbie całkowitej ().

Wyjście

Twój program powinien wypisać na standardowe wyjście dla każdego zapytania minimalną liczbę liczb Fibonacciego potrzebnych do przedstawienia liczby jako ich sumy lub różnicy.

Przykład

Dla danych wejściowych:

1
1070

poprawną odpowiedzią jest:

4

Autor zadania: Karol Pokorski.