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

ми отримаємо

Потім будуть породжуватись відрізки

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

Вхідні дані

Єдине число n (n ≤ 1013).

Вихідні дані

Вивести кількість разів, яку число n зустрічається на відрізку.