Ступеньки лестницы пронумерованы сверху вниз, начиная с единицы. Мальчик скатывает мячик с верхней ступеньки так, что он слетает вниз, ударяясь о некоторые из ступенек. Известно, что мячик во время полёта может перелететь через одну или две расположенные ступеньки (а может и ударяться о каждую).

Определите минимальное количество промежуточных ударов мячика до того, как он ударится о ступеньку с номером N.

Формат входного файла

В единственной строке входных данных записано число N — целая положительная величина (2 ≤ N ≤ 10⁹).

Output

В единственной строке вывести количество промежуточных ударов.

Examples

standard input	standard output
5	1
17	5

Note

В первом примере мячик может удариться о любую из ступенек с номерами 2, 3 или 4, перелетая через остальные.