Последовательность

Рассмотрим отрезок, на концах которого записаны единицы. Далее до бесконечности будем совершать следующую процедуру: для каждого отрезка, на концах которого записаны числа a и b (и внутри которого отсутствуют числа), запишем строго в его середине число a + b. То есть из начального отрезка

мы получим

Затем будут порождаться отрезки

и так далее до бесконечности. Сколько раз на этом отрезке будет записано натуральное число n?

Входные данные

Единственное число n (n ≤ 10^13).

Выходные данные

Вывести количество раз, которое число n встречается на отрезке.

Примеры