eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 19 = 1*2^4+0*2^3+0*2^2+1*2^1+1*2^0 в двоичной системе запишется как 10011). Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик - он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:

10011 11001 11100 01110 00111 10011 ...

и результатом игры, следовательно, окажется число 1*2^4+1*2^3+1*2^2+0*2^1+0*2^0 = 28. Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.

Input data

Ввод содержит одно целое число N (0 <= N <= 32767).

Output data

Ваша программа должна вывести одно целое число, равное результату игры.

Examples

Input example #1
19
Output example #1
28