Цифри та числа
Як багато відкриттів можна здійснити, досліджуючи числа та цифри, з яких вони складаються!
Петрик дуже любить арифметику, і крім домашніх завдань він постійно придумує додаткові задачі. Одного разу він став додавати до натуральних чисел суму цифр, з яких воно складається. Петрик виявив, що деякі числа, наприклад 20, не можуть бути отримані з інших чисел в результаті таких дій. Ці числа йому не сподобались, і він назвав їх некрасивими.
Пізніше, коли Петрик почав вивчати інформатику, ті ж дослідження він став проводити з натуральними числами у двійковій системі числення. Наприклад, двійкове число 1110_2 (у десятковій системі — 14) можна отримати з числа 1100_2 (у десятковій системі — 12), додавши до останнього суму його цифр:
1100_2 + 10_2 = 1110_2.
Петрик вирішив дослідити множину двійкових некрасивих чисел. Перші п'ять некрасивих чисел він знайшов без скдаднощів: 1 = 1_2, 4 = 100_2, 6 = 110_2, 13 = 1101_2, 15 = 1111_2. Продовжити роботу він збирається при допомозі комп'ютера.
Потрібно написати програму, яка визначає кількість двійкових некрасивих чисел, які не перевищують заданого числа n.
Вхідні дані
У першому рядку вхідного файлу міститься число n, записане у десятковій системі числення (1 ≤ n ≤ 10^18).
Вихідні дані
У єдиному рядку вихідного файлу повинно міститись єдине число — кількість двійкових некрасивих чисел, які не перевищують n.