eolymp
bolt
Try our new interface for solving problems
Problems

Забавная игра

Забавная игра

Time limit 1 second
Memory limit 64 MiB

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 data

The input file contains one integer N (0N32767).

Output data

Your program must write to output file a single integer equal to the result of the game.

The input file contains one integer

Examples

Input example #1
19
Output example #1
28