Сайт підготовки до олімпіади з інформатики

Перший тур Волинської учнівської Інтернет-олімпіади з програмування

vippoolimp.byethost14.com

1. Задача BINARY (20 балів)

Ім’я вхідного файлу: BINARY.DAT

Ім’я вихідного файлу: BINARY.SOL

Максимальний час роботи на одному тесті: 3с

Талановитий учень Діма придумав цікаву гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів та одиниць, що починається з одиниці. (Наприклад, десяткове число (19)10 = 1*2^4+0*2^3+0*2^2+1*2^1+1*2^0 в двійковій системі запишеться як (10011)2). Потім вчитель починає зсовувати цифри отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі інші зсовуються на одну позицію вправо), виписуючи утворюються при цьому послідовності з нулів і одиниць у стовпчик - він помітив, що незалежно від вибору вихідного числа виходять послідовності починають з деякого моменту повторюватися. І, нарешті, учень відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом виконаних маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

…

і результатом гри буде число 1*2^4+1*2^3+1*2^2+0*2^1+0*2^0 = 28.

Оскільки придумана гра з числами все більше займає уяву учня, відволікаючи тим самим його від навчання і підготовки до олімпіади, Вас просять написати програму, яка б допомогла Дімі отримувати результат гри без важких ручних обчислень.

Вхідний файл містить одне ціле число N (0<=N<=32767).

Ваша програма повинна вивести в вихідний файл рядок, що містить одне ціле число, рівне результату гри.

Приклад