Starting from a positive integer \(n\), one operation may do exactly one of the following:

• replace \(n\) by \(n/2\) if \(n\) is divisible by \(2\);
• replace \(n\) by \(n/3\) if \(n\) is divisible by \(3\);
• replace \(n\) by \(n-1\).

Find the minimum number of operations needed to reach \(1\).

Input

One line containing \(n\).

The input satisfies:

• \(1 \le n \le 10^6\)

Output

Print the minimum number of operations.

Example

Input

10

Output

3

Explanation

One optimal sequence is 10 -> 9 -> 3 -> 1, which uses three operations.