Problem description

Operacją prostą na napisie S nazwiemy jedną z poniższych operacji:

• zamień literę w S na dowolną inną literę,
• usuń dowolną literę z S,
• dodaj dowolną literę do S na dowolnej pozycji.

Odległość edycyjna pomiędzy dwoma napisami A i B to minimalna liczba operacji prostych, które pozwolą na transformację A w B. Dla przykładu odległość edycyjna między wyrazami ląd oraz lont ma wartość 3.

W tym zadaniu Jasiu prosi Cię o pomoc w rozwiązaniu pracy domowej na interaktywne zajęcia matematyki. Jego nauczycielka wprowadziła ostatnio pojęcie liczb Fibonacciego, a żeby dobrze je utrwalić w pamięci uczniów wypisała na tablicy pewną liczbę N i zapytała: Jaka jest najmniejsza odległość edycyjna pomiędzy N a dowolną liczbą Fibonacciego?

Przypomnijmy tylko, że ciąg liczb Fibonacciego zaczynamy od liczb 0 i 1, a każda kolejna liczba jest sumą dwóch poprzednich.

Jak zapewne nie trudno się domyślić to zadanie przerosło Jasia, więc postanowił poprosić Cię o pomoc. Napisz program, który wczyta ze standardowego wejścia liczbę N i wypisze na standardowym wyjściu odpowiedź na pytanie zadane przez nauczycielkę Jasia.

Wejście

W pierwszym (jedynym) wierszu standardowego wejścia znajduje się jedna liczba całkowita N.

Wyjście

W pierwszym (jedynym) wierszu standardowego wyjścia powinna znaleźć się jedna liczba całkowita oznaczająca minimalną odległość edycyjną liczby N do dowolnej liczby Fibonacciego.

Ograniczenia

0 ≤ N ≤ 10⁹.

Przykłady

3

0

66

2