Fun Game

The legendary mathematics teacher Yuri Petrovich invented a fun game with numbers. He takes an arbitrary integer and converts it into the binary number system, obtaining a sequence of zeros and ones that begins with one. (For example, decimal 19_{10} = 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 in the binary system is written as 10011_2.) The teacher then begins to cyclically shift the digits of the obtained binary number (so that the last digit becomes the first, and all others shift one position to the right), writing down the resulting sequences of zeros and ones in a column. He observed that, regardless of the initial number, the resulting sequences eventually start to repeat. Finally, Yuri Petrovich finds the maximum among the written numbers and converts it back into the decimal number system; he considers this number the result of the manipulations. For the number $19$, the list of sequences is as follows:

$10011$

$11001$

$11100$

$01110$

$00111$

$10011$

…

and the result of the game, therefore, is the number 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 = 28.

Since the invented game with numbers increasingly occupies the teacher's imagination and distracts him from his work with very gifted pupils, you are asked to write a program to help Yuri Petrovich obtain the result of the game without tedious manual calculations.