There are three types of operations that can be performed on an integer:
If the number is divisible by , divide it by ;
If the number is divisible by , divide it by ;
Subtract .
For a given positive integer , find the minimum number of operations required to obtain .
Each line contains a single positive integer .
For each value of , print the minimum number of operations required to obtain on a separate line.