Забавная игра
The legendary mathematics teacher Yuri Petrovich invented a fun game with numbers. Namely, taking an arbitrary integer, it converts it into binary number system, receiving a sequence of zeros and ones, beginning with one. (For example, decimal 19_10 = 1×2^4+0×2^3+0×2^2+1×2^1+1×2^0 in the binary system is written as 10011_2). The teacher then begins to move the figures obtained by the binary number for the cycle (so that the latter figure is the first and the rest are shifted one position to the right), by inserting formed in this sequence of ones and zeros in a column - he noticed that whatever the initial number the resulting sequence starting from some instant repeat. And finally, Yuri Petrovich finds the maximum of prescription numbers and translates it back into the decimal number system, counting the number of completed procedures. Thus, for a list of the 19 sequences is as follows:
10011
11001
11100
01110
00111
10011
…
and the result of the game, therefore, be the number of 1×2^4+1×2^3+1×2^2+0×2^1+0×2^0 = 28.
Since the game was invented with the numbers increasing teacher takes imagination, thus distracting him from his work with gifted pupils very well, you are asked to write a program which would help them get to Yuri Petrovich outcome of the game without the tedious manual calculations.
and the result of the game, therefore, be the number of
Input
The input file contains one integer N (0 ≤ N ≤ 32767).
Output
Your program must write to output file a single integer equal to the result of the game.
The input file contains one integer