Make 1 (Part 3)

For an integer $X$, there are three allowed operations.

1. If $X$ is divisible by 3, divide it by 3.
2. If $X$ is divisible by 2, divide it by 2.
3. Subtract 1 from $X$.

Given an integer $N$, use these three operations as needed to make 1. Print the minimum number of operations needed.

The first line contains an integer $N$ with $1 \le N \le 10^{18}$.

Print the minimum number of operations on the first line.

For $N = 10$, you can make 1 in 3 operations: 10 → 9 → 3 → 1.