Problem description

Zachowanie Jasia ostatnio zaczęło bardzo odbiegać od normy. Zafascynował się ciągiem Fibonacciego. Różne są jego definicje, ale w tym zadaniu przyjmiemy, że jest to ciąg rozpoczynający się od dwóch jedynek, w którym każdy kolejny element jest sumą dwóch poprzednich elementów (1, 1, 2, 3, 5, 8, 13, …). W szczególności, zakładamy, że 0 nie jest liczbą Fibonacciego.

Samo zafascynowanie nie byłoby jeszcze czymś dziwnym, ale Bajtek widzi teraz liczby Fibonacciego dosłownie wszędzie. Przykładowo: w liczbie 12 nie ma prawdopodobnie zbyt wiele specjalnego, a już w szczególności w kontekście liczb Fibonacciego.

Bajtek powiedziałby jednak coś takiego: Przecież jeśli wziąć resztę z dzielenia liczby 12 przez 7, to dostajemy 5, czyli liczbę Fibonacciego! Zapewne prawie o każdej liczbie można by tak powiedzieć: wszystkie liczby nieparzyste dają resztę 1 (czyli liczbę Fibonacciego) przy dzieleniu przez 2, wszystkie liczby niepodzielne przez 3 dają reszty 1 lub 2 (czyli ponownie liczby Fibonacciego) przy dzieleniu przez 3, więc niewiele w tym specjalnego.

Bajtek dla każdej liczby X potrafi podać bardzo dużo przykładów liczb M, że reszta z dzielenia liczby X przez M jest liczbą Fibonacciego. A to już podejrzane. Może rzeczywiście jest tak, że każda liczba ma coś w sobie z liczby Fibonacciego? Czy możesz to sprawdzić?

Napisz program, który: wczyta liczbę X, wyznaczy liczbę wartości M < X, takich, że reszta z dzielenia X przez M jest liczbą Fibonacciego i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna X.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć liczba różnych wartości M < X, że reszta z dzielenia X przez M jest liczbą Fibonacciego.

Ograniczenia

1 ≤ X ≤ 10¹².

Przykład

12

5