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 ≤ 106).

Output

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