Under construction

Still being built. Things may change

Make It One

Interview

Time limit0.15sMemory limit128 MB

Summary
Compute the minimum number of divide-by-3, divide-by-2, or subtract-1 operations needed to reduce N to 1.
Level

Easy3 of 10

Topics
Dynamic programming, Math
Solved
No attempts yet

Problem

For an integer X, you may use the following three operations.

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

Given an integer N, use these operations in any order to make N equal to 1. Find the minimum possible number of operations.

Input

The first line contains an integer N. (1 <= N <= 1,000,000)

Output

Print the minimum number of operations needed.

Hint

For N = 10, one optimal sequence is 10 -> 9 -> 3 -> 1, which uses 3 operations.

Examples2

  1. Example 1

    Input
    2
    Expected output
    1

  2. Example 2

    Input
    10
    Expected output
    3