Remote Training on Programming

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы. (Например, десятичное число 19₁₀ = 1×2⁴+0×2³+0×2²+1×2¹+1×2⁰ в двоичной системе запишется как 10011₂.) Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик — он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:

10011

11001

11100

01110

00111

10011

…

и результатом игры, следовательно, окажется число 1×2⁴+1×2³+1×2²+0×2¹+0×2⁰ = 28.

 

Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, Вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.

Формат входных данных

Входной файл содержит одно целое число N (0£N£32767).

Формат выходных данных

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

Пример

Входные данные	Выходные данные
19	28