Є калькулятор, який виконує три операції:

• Додати до \(X\) одиницю.
• Помножити число \(X\) на 2.
• Помножити число \(X\) на 3.

Визначте, яке найменше число операцій необхідно для того, щоб отримати з числа 1 задане число \(N\).

Формат вхідних даних

Програма отримує на вхід одне число, що не перевищує \(10^6\).

Формат вихідних даних

Вивести відповідь.

Приклад вхідних даних

1

Приклад вихідних даних

0

Приклад вхідних даних

5

Приклад вихідних даних

3

Приклад вхідних даних

32718

Приклад вихідних даних

17