C. Number Machine
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Harry has a strange number machine that has two buttons. The machine has a number $$$x$$$ on its screen. If button A is pressed, the number on the screen changes to $$$3x+2$$$. If button B is pressed, the number on the screen changes to $$$x+1$$$. The initial number on the machine is 1, and Harry wants to change the number to $$$n$$$. Harry is lazy so he wants to press the least number of buttons possible.

What is the minimum number of button presses Harry has to make in order to obtain the number $$$n$$$?

Input

The first line contains the integer $$$n$$$ ($$$1\le n\le 10^{18}$$$).

Output

Output a single integer denoting the minimum number of button presses.

Examples
Input
5
Output
1
Input
20
Output
3