eolymp
bolt
Try our new interface for solving problems
Problems

Decreasing Number

Decreasing Number

Time limit 1 second
Memory limit 128 MiB

There are three types of operations that can be performed on an integer:

  • If the number is divisible by 3, divide it by 3;

  • If the number is divisible by 2, divide it by 2;

  • Subtract 1.

For a given positive integer n, find the minimum number of operations required to obtain 1.

Input data

Each line contains a single positive integer n~(1 \le n \le 10^6).

Output data

For each value of n, print the minimum number of operations required to obtain 1 on a separate line.

Examples

Input example #1
1
5
10
Output example #1
0
3
3