Розглянемо відрізок, на кінцях якого записані одиниці. Далі до нескінченності будемо здійснювати наступну процедуру: для кожного відрізка, на кінцях якого записані числа a та b (і всередині якого відсутні числа), запишемо строго у його середині число a + b. Тобто з початкового відрізка
ми отримаємо
Потім будуть породжуватись відрізки
і так далі до нескінченності. Скільки разів на цьому відрізку буде записано натуральне число n?
Єдине число n (n ≤ 10^13
).
Вивести кількість разів, яку число n зустрічається на відрізку.