Все, наверное, помнят детскую загадку: A и B сидели на трубе. A упало, B пропало. Что осталось на трубе?.

Вася, Петя и Дима играют в похожую, придуманную ими игру. Для начала они выписали в ряд числа от 1 до n и пронумеровали их, с удивлением обнаружив, что порядковый номер равен самому числу. Далее они по очереди делают ходы. Сначала из этого ряда первый играющий вычёркивает все числа, стоящие на четных местах. Далее, в оставшемся ряду чисел удаляют те, которые стоят в нем на нечетных местах, предварительно по-новому пронумеровав числа, что остались. Потом те, которые стоят в оставшемся после первых двух операций ряду на местах, номера которых кратны трем. Затем - снова на четных местах, на нечетных, на местах, кратных трем и т.д. Вычеркивания производят до тех пор, пока не останется одно число.

Какое число останется последним не вычеркнутым в результате этой игры?

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

Количество натуральных чисел n (1 ≤ n ≤ 108), записанных на игровом поле.

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

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