Задача 38431. funny game

The legendary math teacher Yuri Petrovich came up with a fun game with numbers. Namely, taking an arbitrary integer, he translates it into a binary number system, getting some sequence of zeros and ones, starting with one. (For example, decimal 1910 = 1·2⁴+0·2³+0·2²+1·2¹ +1·2⁰ in binary system will be written as 10011₂.) Then the teacher starts shifting the digits of the resulting binary number around the cycle (so that the last digit becomes the first , and all the rest are shifted one position to the right), writing out the resulting sequences of zeros and ones in the column — he noticed that regardless of the choice of the initial number, the resulting sequences begin to repeat from a certain moment. And, finally, Yuri Petrovich finds the maximum of the numbers written out and translates it back into the decimal number system, considering this number the result of the manipulations done. So, for the number 19, the list of sequences would be:
10011
11001
11100
01110
00111
10011
…
and the result of the game will therefore be the number 1·2⁴+1·2³+1·2²+0·2 ¹+0·2⁰ = 28.

Since the invented game with numbers takes more and more of the teacher's imagination, thereby distracting him from working with very gifted schoolchildren, you are asked to write a program that would help Yuri Petrovich get the result of the game without tedious manual calculations.
Input format
The input file contains one integer N (0 ≤ N ≤ 32767).
Output format
Your program should print to the output file a single integer equal to the result of the game.

Examples

#	Input	Output
1	19	28