You are the captain of the StarRunner, an interstellar courier ship delivering critical supplies between outposts on a vast one-dimensional space lane.

Your ship:

• Always begins at position 0.
• Starts with a forward thrust level of +1.

To move, your ship's AI accepts three kinds of thruster commands:

1. Accelerate (A)

position += thrust thrust *= 2

You cover more distance as your thrusters amplify exponentially.

2. Reverse (R)

If thrust > 0, then thrust -= 1

otherwise thrust += 1

The ship's position does not change.

(You flip direction at a base thrust.)

3. Brake (B)

If thrust > 0 thrust = max(1, thrust / 2)

Otherwise thrust = min(-1, thrust / 2)

Position remains unchanged.

(You cut your thruster power in half to fine-tune your approach.)

Because the space lane extends infinitely in both directions, you may overshoot the destination or move into negative coordinates before reversing.

Given an integer target, determine the minimum number of commands required to stop exactly at position target.

Input

target

Output

Print the minimum number of commands.

Explanation

One optimal sequence of commands is:

A A B A