Problem F
Longest Collatz Chain

The Collatz conjecture says that if you take a positive integer $n$ and repeat the following procedure you always end up at $1$. If the number is even you divide it by two, and otherwise you multiply by three and add one. Dividing by two or multiplying by three and adding one both count as one step.

We want to find what number $<n$ takes the highest number of steps before ending at $1$.

Input

The first and only line of input contains a positive integer $n\le {10}^6$.

Output

Print the number $<n$ that takes the most steps before reaching one. If there are ties, print the smaller number.

100000

77031