Competitions

# Dynamic programming - linear

# Decreasing Number

There are three types of operations you can perform on an integer:

`1.`

If it's divisible by **3**, divide it by **3**.

`2.`

If it's divisible by **2**, divide it by **2**.

`3.`

Subtract **1**.

Given a positive integer **n**, find the minimal number of operations needed to produce the number **1**.

#### Input

Each line contains the positive integer **n** (**1** ≤ **n** ≤ `10`

).^{6}

#### Output

For each value of **n** print in a separate line the minimal number of operations needed to produce the number **1**.

Input example #1

1 5 10

Output example #1

0 3 3