Fun game
Legendary mathematics teacher Yuriy Petrovych has devised an entertaining game involving numbers. He starts with any integer and converts it into its binary representation, which is a sequence of zeros and ones beginning with one. For instance, the decimal number **19** is represented in binary as **10011** (since **19** = **1***2^4 + **0***2^3 + **0***2^2 + **1***2^1 + **1***2^0).
Next, Yuriy Petrovych cyclically shifts the digits of this binary number. This means the last digit moves to the front, and all other digits shift one position to the right. He writes each new sequence of zeros and ones in a column. He observed that these sequences eventually start to repeat, regardless of the initial number chosen.
Finally, Yuriy Petrovych identifies the maximum value among these sequences and converts it back to the decimal system, considering this number as the result of his manipulations. For the number **19**, the sequences generated are:
**10011, 11001, 11100, 01110, 00111, 10011** ...
The result of the game, therefore, is the number **28**, calculated as **1***2^4 + **1***2^3 + **1***2^2 + **0***2^1 + **0***2^0.
Since this game increasingly fascinates Yuriy Petrovych, distracting him from teaching his exceptionally talented students, you are tasked with writing a program to help him obtain the result of the game without the need for tedious manual calculations.
Input
The input consists of a single integer **N** (**0** <= **N** <= **32767**).
Output
Your program should output a single integer, which is the result of the game.