Mathematics teacher Yuri Petrovich
Problem
Legendary math teacher Yuri Petrovich came up with a funny 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 number\(19_{10} = 1\cdot2^4+0\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0 \ ) in binary system will be written as 10011 2.) Then the teacher begins to shift the digits of the resulting binary number in a cycle (so that the last digit becomes the first, and all the others 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 a number \(1\cdot2^4+1\cdot2^3+1\cdot2^2+0\cdot2^1+0\cdot2^0 = 28_{ 10} \)
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:
The input file contains a single integer N (0<=N<=32767).
Output:
Your program should print to the output file a single integer equal to the result of the game.
Examples