Усі, напевне, пам'ятають дитячу загадку: A і B сиділи на трубі. A упало, B пропало. Що лишилось на трубі?

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

Яке число залишиться останнім не викресленим в результаті цієї гри?

Вхідні дані

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

Вихідні дані

Виведіть число, яке залишиться останнім не викресленим в результаті цієї гри.