Забавна гра
Легендарний вчитель математики Юрій Петрович придумав забавну гру з числами. А саме, взявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів та одиниць, яка починається з одиниці. (Наприклад, десяткове число 19 = 1*2^4+0*2^3+0*2^2+1*2^1+1*2^0 у двійковій системі запишеться як 10011). Після цього вчитель починає здвигати цифри отриманого двійкового числа по циклу (так, що остання цифра становиться першою, а всі інші переміщуються на одну позицію праворуч), виписуючи утворені при цьому послідовності з нулів та одиниць в стовбчик - він помітив, що незалежно від вибору заданого числа отримані послідовності починають з деякого моменту повторюватись. І, нарешті, Юрій Петрович відшукує максимальне з виписаних чисел і переводить його назад у десяткову систему числення, вважаючи це число результатом зроблених маніпуляцій. Так, для числа 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).
Вихідні дані
Ваша програма повинна вивести одне ціле число, рівне результату гри.