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