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

10011
11001
11100
01110
00111
10011
...

і результатом гри, відповідно, виявиться число 1*2⁴+1*2³+1*2²+0*2¹+0*2⁰ = 28. Оскільки придумана гра з числами все більше захоплює уяву вчителя, відволікаючи тим самим його відт роботи з ну дуже обдарованими школярами, Вас просять написати програму, яка б допомогла Юрію Петровичу отримувати результат гри без втомлюючих ручних обчислень.

   Вхідні дані

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

   Вихідні дані

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