All of you probably remember a children's riddle: A and B were sitting on the tube. A is fell, B is lost. What is left on the tube?

Vasya, Petya and Dima play a similar, they invented the game. For a start they were discharged in a number of numbers from 1 to n, and numbered them, was surprised to find that the serial number is equal to the number itself. Then they in turn make their moves. First of this series is the first game striking out all the numbers on even ground. Further, in the remaining series of numbers are removed, those who stand in it in odd places, a new pre-numbered the number that remain. Then those who are remaining in the first two series of operations on the ground, whose numbers are divisible by three. Then - again on even ground, the odd, on the ground that are multiples of three, etc. Deletions produce long until there is a single number.

What number will not last deleted as a result of this game?

Input

The number of positive integers n (1 ≤ n ≤ 108), recorded on the playing field.

Ouput

Print the last not deleted number as a result of this game.