Забавна гра

Легендарний учитель математики Юрій Петрович придумав забавну гру з числами. Він бере довільне ціле число і переводить його у двійкову систему числення, отримуючи послідовність з нулів та одиниць, що починається з одиниці. (Наприклад, десяткове число 19_{10} = 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 у двійковій системі записується як 10011_2.) Потім учитель починає циклічно зсувати цифри отриманого двійкового числа (так, що остання цифра стає першою, а всі інші зсуваються на одну позицію праворуч), виписуючи утворені послідовності з нулів і одиниць у стовпчик. Він помітив, що незалежно від вибору початкового числа отримані послідовності з певного моменту починають повторюватися. Нарешті, Юрій Петрович знаходить максимальне з виписаних чисел і переводить його назад у десяткову систему числення; це число він вважає результатом маніпуляцій. Для числа $19$ список послідовностей буде таким:

$10011$

$11001$

$11100$

$01110$

$00111$

$10011$

…

і результатом гри, відповідно, буде число 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 = 28.

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