Двійкове число

Планета Шелезяка... Корисних копалин на планеті нема. Води також нема. Атмосфери нема. Нічого на планеті нема. Якщо що й було, роботи усе витратили і живуть у бідності.

Кір Буличов "Подорож Аліси"

Як відомо, планета Шелезяка розміщена у віддаленій частині нашої Галактики, у стороні від космічних трас. Воду роботи (єдині мешканці планети у другій половині 21-го століття) ліквідували спіціально, щоб не іржавіти (вони опасались ливнів та повеней). У зв'язку з цим планета виявилась остаточно нікому крім роботів не потрібна.

Одного разу на пустинну планету прилетіли пірати. То були справжні досвідчені злодії. Їх серцю жалість була невідома. Вони захопили майже усіх роботів і вивезли їх у далеку-предалеку галактику і заставили працювати на шахтах на планеті Бендосвіт.

Пройшло чимало часу, ніж про це стало відомо на Землі. Річард Темпест, хоробрий співробітник інституту Часу, відправився у минуле з метою перешкодити диявольским планам піратів. Як виявилось, користуючись гостинністю роботів, пірати пропонували роботам розв'язати задачку на швидкість. Проте обчислювальні можливості роботів були не великі, а оптимізувати алгоритми їх роботи було нікому. Тому все, що залишалось злодіям — завантажити у трюм корабля бездушні тіла роботів, поринутих у обчислення.

Річарду вдалось взнати, над чим безуспішно бились електронні мізки роботів. Пірати пропонували їм ціле невід'ємне число n. Після цього вони просили взнати, що відбудеться з цим числом, якщо до нього n раз застосувати операцію: взяти старший біт у двійковому запису числа і поставити його в кінець. Наприклад, якщо один раз застосувати цю операцію до числа $14_{10}$ = $1110_2$, отримаємо $13_{10}$ = $1101_2$. Після повторного застосування буде отримано $11_{10}$ = $1011_2$.

Річард присвиснув. Якщо йому вдасться дістати програму, яка швидко розв'язує цю задачу, він зможе відправитись у часі до прильоту піратів і завантажити у роботів цю програму, щоб вони змогли протичтояти злобним піратам.

Ви - співробітник інституті Часу, якому доручено у терміновому порядку написати цю програму. Допоможіть врятувати роботів.

Вхідні дані

Ціле число $n$ (0 ≤ $n$ ≤ $10^{18}$).

Вихідні дані

Виведіть відповідь до задачі, поставленої піратами перед роботами.

Приклади