eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

prb3648-01

мы получим

prb3648-02

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

prb3648-03

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

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

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

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

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

Пример

Входные данные #1
4
Выходные данные #1
2
Источник III Международная Летняя школа программирования 2012 г. Севастополь