e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Decreasing Number

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 (1n106).

Output

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

Time limit 1 second
Memory limit 128 MiB
Input example #1
1
5
10
Output example #1
0
3
3