There exists a famous unsolved problem in mathematics called the Collatz Conjecture, that states the following:

Starting at a positive integer ~n~, a specific sequence will always reach ~1~ following these rules:

• If ~n~ is even, divide it by two.
• If ~n~ is odd, it becomes ~3n + 1~.

For all positive integers below or equal to a number ~m~, you are interested in finding the number which takes the most steps to reach 1.

Input

The input consists of a single integer input ~m~ ~(1 \leq m \leq 1000)~.

Output

Output a single integer, the starting number which results in the most steps to reach 1. If there are multiple integers which result in the most steps, output the largest one.

Example

Input

5

Output

3

Starting at ~3~, we take ~7~ steps to reach ~1~.

• ~3~ is odd, ~(3 * 3) + 1 = 10~.
• ~10~ is even, ~10 / 2 = 5~.
• ~5~ is odd, ~(3 * 5) + 1 = 16~.
• ~16~ is even, ~16 / 2 = 8~.
• ~8~ is even, ~8 / 2 = 4~.
• ~4~ is even, ~4 / 2 = 2~.
• ~2~ is even, ~2 / 1 = 1~.

It can be proven that there is no number less than or equal to ~5~ that takes more steps to reach ~1~.

Example 2

Input

1

Output

1

There is only one number to test — 1, which since is already at 1, takes 0 steps.