e-olymp
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